Quicksort: Difference between revisions
No edit summary |
No edit summary |
||
| Line 5: | Line 5: | ||
The goal is at each iteration to select a pivot (can be randomly chosen) and to rebuild the array with all the elements smaller that the pivot on the left and all the elements bigger that the pivot on the right. Then, we have to run the algorithm again in both left and right sub-arrays around the pivot. | The goal is at each iteration to select a pivot (can be randomly chosen) and to rebuild the array with all the elements smaller that the pivot on the left and all the elements bigger that the pivot on the right. Then, we have to run the algorithm again in both left and right sub-arrays around the pivot. | ||
There are two main partition scheme: | |||
* Lomuto partition scheme | |||
* Hoare partition scheme | |||
=== Lomuto partition scheme === | |||
For instance, if we always choose the rightmost element of the array as the pivot, the wall starts before the leftmost element, each element smaller than the pivot should be swapped with the closest element from the right of the wall, then the wall should be shifted to one element on the right to get that smaller element on the left side of the wall. Eventually, swap the pivot with the element just on the right side of the wall. What you will get is an array with the pivot that has all his smaller elements on the left and the bigger elements on the right. | For instance, if we always choose the rightmost element of the array as the pivot, the wall starts before the leftmost element, each element smaller than the pivot should be swapped with the closest element from the right of the wall, then the wall should be shifted to one element on the right to get that smaller element on the left side of the wall. Eventually, swap the pivot with the element just on the right side of the wall. What you will get is an array with the pivot that has all his smaller elements on the left and the bigger elements on the right. | ||
Revision as of 03:37, 11 June 2018
Quicksort is an exchange sorting algorithm.
The Quicksort involves the concepts of pivot and wall.
The goal is at each iteration to select a pivot (can be randomly chosen) and to rebuild the array with all the elements smaller that the pivot on the left and all the elements bigger that the pivot on the right. Then, we have to run the algorithm again in both left and right sub-arrays around the pivot.
There are two main partition scheme:
- Lomuto partition scheme
- Hoare partition scheme
Lomuto partition scheme
For instance, if we always choose the rightmost element of the array as the pivot, the wall starts before the leftmost element, each element smaller than the pivot should be swapped with the closest element from the right of the wall, then the wall should be shifted to one element on the right to get that smaller element on the left side of the wall. Eventually, swap the pivot with the element just on the right side of the wall. What you will get is an array with the pivot that has all his smaller elements on the left and the bigger elements on the right.
Now, let's do the same thing on the opposite direction: we want to choose the pivot from the left. Therefore, the wall will start on the right. All element bigger than the pivot will be swapped with the closest element of the wall from the left, then the wall should be shifted on the left.
Resources
| https://www.youtube.com/watch?v=SLauY6PpjW4 |
| https://en.wikipedia.org/wiki/Quicksort |