This is the most extensively used internal sorting algorithm. In its fundamental form, it was invented by C.A.R. Hoare in the year of 1960. Its popularity lies in the easiness of implementation, moderate use of resources & acceptable behavior for a variety of sorting cases. The fundamental of quick sort is the divide & conquer strategy that means Divide the problem [list to be sorted] into sub-problems [sub-lists], till solved sub problems [sorted sub-lists] are found. It is implemented as follows:
Select one item A[I] from the list A[ ].
Rearrange the list so that this item come to the appropriate position, that means all preceding items have a lesser value and all succeeding items contain a greater value than this item.
1. Place A[0], A[1] .. A[I-1] in sublist 1
2. A[I]
3. Place A[I + 1], A[I + 2] ... A[N] in sublist 2
Repeat steps 1 and step 2 for sublist1 and sublist2 until A[ ] is a sorted list. As can be seen, this algorithm contains a recursive structure.
The divide' procedure is of utmost importance in this algorithm. Usually this is implemented as follows:
1. Select A[I] as the dividing element.
2. From the left end of the list (A[O] onwards) scan until an item A[R] is found whose value is greater than A[I].
3. From the right end of list [A[N] backwards] scan until an item A[L] is found whose value is less than A[1].
4. Swap A[R] & A[L].
5. Continue steps 2, 3 & 4 till the scan pointers cross. End at this stage.
6. At this point, sublist1 and sublist2 are ready.
7. Now do the same for each of sublist1 & sublist2.