Quicksort: Difference between revisions
No edit summary |
No edit summary |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
Quicksort is an exchange sorting algorithm. | Quicksort is an exchange sorting algorithm. | ||
The | The goal is at each iteration to select a pivot (that 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 schemes: | |||
* Lomuto partition scheme | |||
* Hoare partition scheme | |||
=== Lomuto partition scheme === | |||
This partition scheme involves the concepts of pivot and wall. | |||
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 | 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 the 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 elements 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. | |||
=== Hoare partition scheme === | |||
Given a pivot number in the array, the partition algorithm looks, from the left of the array, to the first element greater or equal than the pivot and, from the right of the array, the first element less or equal than the pivot and switch them. Then, it continues to look for an element greater than the pivot from the left and smaller than the pivot from the right to switch them. The partition stops when the left and right cursors meet. The partition scheme is recursively applied on the left and the right side of the array. The delimitation of the right and left side is determined by where the index where the cursors meet. | |||
==Resources== | ==Resources== | ||
| Line 13: | Line 21: | ||
! | ! | ||
|- | |- | ||
| | |https://www.youtube.com/watch?v=SLauY6PpjW4 | ||
|- | |||
|https://en.wikipedia.org/wiki/Quicksort | |||
|} | |} | ||
Latest revision as of 05:56, 14 June 2018
Quicksort is an exchange sorting algorithm.
The goal is at each iteration to select a pivot (that 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 schemes:
- Lomuto partition scheme
- Hoare partition scheme
Lomuto partition scheme
This partition scheme involves the concepts of pivot and wall.
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 the 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 elements 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.
Hoare partition scheme
Given a pivot number in the array, the partition algorithm looks, from the left of the array, to the first element greater or equal than the pivot and, from the right of the array, the first element less or equal than the pivot and switch them. Then, it continues to look for an element greater than the pivot from the left and smaller than the pivot from the right to switch them. The partition stops when the left and right cursors meet. The partition scheme is recursively applied on the left and the right side of the array. The delimitation of the right and left side is determined by where the index where the cursors meet.
Resources
| https://www.youtube.com/watch?v=SLauY6PpjW4 |
| https://en.wikipedia.org/wiki/Quicksort |