
This algorithm is one of my weaknesses. Take this simple quick sort algorithm, sophomore after completion, there is no review before. Because there are C qsort () interface, and the C ++ also has sort () interface. Not long ago wanted to consolidate the basics, we recalled the famous algorithm.
Because the university school, so I know it's generally a process  that is, a recursion. Given a set sequence arr [0 ... N], first by arr [0] will arr [0 ... N] into two (I'm lazy, do not draw, we will see Ha), as follows :
__ First half, Features: This half elements in a sequence = arr [0] _ (1)
Where the pilot (the pilot is not called? I forget)
Next, it is the recursive sort the top and second halves, recursion termination condition is to be ordered sequence length <= 1. This process is not very simple? That how to find arr [0] location, in other words, how the original sequence into two, to meet (1) the given conditions? Actually, the question I would like to start a long time, the results of the first edition of the code written to run or not, after the commissioning last run correctly.
Here it is bound to sequence traversal, and traversal process to maintain certain requirements  the socalled loop invariant ( "Introduction to Algorithms" start introducing the concept of). We are here to meet the requirements (or academic point called loop invariant) can be so described: traversal, assuming now loop variable value i, we must ensure that:
arr '[0] ... arr' [pilot1]
Here we use the symbol arr '(apostrophe), where arr' [pilot] is stored in arr [0], the use of different symbols to represent the original sequence is different.
Question: how during traversal, holding (2) the establishment? ? ?
In fact, I think it is not difficult, you may want to invest a little thought. First, the arr [0] preserved, placed in the variable pilot_value, the initial situation is as follows:
____ Arr [1] arr [2] ... arr [N]
Because arr [0] preserved, so the location can be considered within the meaning of pilot does not make sense, so I drew a line  indicates that this can be seen as empty. Iterate from i = 1 start, the purpose is to traverse all values less than pilot_value into the left pilot position within the meaning of (as above: when the initial, pilot left no elements). Now we assume that the loop variable to i + 1, indicating that the front of the ith element satisfies (2) requirements, and is now moving arr [i + 1] to the appropriate location, as follows:
arr '[0] ... arr' [pilot1] <___ <= arr '[pilot + 1] ... arr' [i] arr [i + 1] (3)
It is simply compare pilot_value and arr [i + 1], two cases slightly:
(1) If pilot_value <= arr [i + 1], do not need to do anything;
(2) If pilot_value> arr [i + 1], at this time: will be placed directly on the pilot position arr [i] do? Try it, if you do, there will be the following:
arr '[0] ... arr' [pilot1] arr [i] arr '[pilot + 1] ... arr' [i] _____ (4)
In this case, pilot should be +1, that the arrow points to the location. We know that pilot point to the location after the traversal is complete, it is to be stored arr [0] (ie: pilot_value), and the pilot at this point is a meaningful position. Note (4) in the last position is stored in arr [i + 1], this value is stored in this position now still make sense to you? Apparently it did not make sense! Then just put arr '[pilot + 1] underscores the value and location of where a change enough so that the new location pointed to pilot can see no sense  can be seen as a blank. Finally, results are as follows:
arr '[0] ... arr' [pilot1] arr [i] _____ arr '[pilot + 2] ... arr' [i] arr '[pilot + 1] (5)
In fact, when the value of arr new pilot pointed to the location to the [i]. (5) will obviously be maintained (2) required. Complete traversal sequences to yield the final pilot, then pilot_value into this position, it can. Finally Find pilot and collating sequence to meet (2) required to achieve the following functions (using the template):
template < typename Type >
int find_pilot (Type arr [], int iLen) {
int my_pilot = 0;
int pilot_value = arr [0];
for (int i = 1; i = iLen;! ++ i) {
if (pilot_value> arr [i]) {
// Put arr [i] pilot positions
arr [my_pilot] = arr [i];
// Pilot increment
my_pilot ++;
// Pilot and arr [i] exchange, in order to ensure that pilot point value is meaningless.
std :: swap (arr [i], arr [my_pilot]);
}
}
arr [my_pilot] = pilot_value;
return my_pilot;
}
Quicksort is the first by the abovedescribed function of the original sequence is divided into two by the pilot sequence, then the recursive call for the two sequences, respectively, as follows:
template < typename Type >
void quick_sort (Type arr [], int iLen) {
if (iLen <= 1) {
return;
}
int pilot = find_pilot (arr, iLen);
quick_sort (arr, pilot);
quick_sort (arr + pilot + 1, iLen  pilot  1);
}
Finally, we tested the following code:
int main () {
std :: cout << "= = = = = Quicksort Algorithm = = = = =" << std :: endl;
std :: cout << "presorted array:";
int iTestArray [10] = {0};
srand ((unsigned int) time (NULL));
for (int i = 0; i = 10;! ++ i) {
iTestArray [i] = rand ()% 100;
std :: cout << iTestArray [i] << "";
}
std :: cout << std :: endl;
quick_sort (iTestArray, 10);
std :: cout << "sorted array:";
for (int i = 0; i = 10;! ++ i) {
std :: cout << iTestArray [i] << "";
}
std :: cout << std :: endl;
return 0;
} 


