Quick Sort:-
Steps for doing quick sort -
- Select an element as pivot from the list.
- Divide the list into two parts such that all the elements on the left side of the pivot are smaller than pivot and the elements on the right side are greater than pivot.
- Store the pivot at its correct position in between the two lists.
- One element has reached at its correct position.
- Repeat steps 1-3 for each of the sub-lists created.
- Stop the process untill one element is left in each of the sub-list.
Quick_Sort(low, high)
1. If(low > high)
Return
2. Set pivot = arr[low]
3. Set i = low +1
4. Set j = high
5. Repeat step 6 until i > high or arr[i] >pivot than
6. Increment i by 1
7. Repeat step 8 until j < low or arr[j] < pivot than
8. Decrement j by 1
9. If i < j
swap arr[i] with arr[j]
10. If i <= j
go to step 5.
11. If low < j
swap arr[low] with arr[j]
12. Quick_Sort (low, j-1)
13. Quick_Sort (j+1, high)
Example:-
1. 28 55 46 38 16 89 83 30
|
pivot
-------------------------> Greater value
2. 28 55 46 38 16 89 83 30
<------------------- Smaller value
3. 28 55 46 38 16 89 83 30
|| ||
SWAP
4. 28 16 46 38 55 89 83 30
smaller <-------
|
5. 28 16 46 38 55 89 83 30
|
----------> greater value
6. 28 16 46 38 55 89 83 30
| |
No change as smaller value is already on the left
7. Divide the list.
28 16 46 38 55 89 83 30
List A List B
8. Swap 16 with 28 in A
16 28 // truncate pivot from A
16 // only one element left no sorting req.
9. Similarly, repeat the process for list B.
10. 16 46 38 55 89 83 30
11. 16 28 46 38 30 89 83 55
| | List C
SWAP
12. 16 28 30 38 46 89 83 55
13. Repeat the process until all the lists don't get sorted.
14. After that merge them. Sorted list will be -
16 28 30 38 46 55 83 89
