Please enable JavaScript.
Coggle requires JavaScript to display documents.
Quicksort, It's worth stopping the scans
after encountering an…
Quicksort
-
-
1.We start by selecting a pivot(an element with respect to whose value we are going to divide the subarray).
2.We scan the subarray from both ends,
comparing the subarray’s elements to the pivot.
The left-to-right scan starts with the second element. This scan skips over elements that are smaller than the pivot and stops upon encountering the first element greater than or equal to the pivot.
The right-to-left scan, starts with the last element of the subarray. This scan skips over elements that are larger than the pivot and stops on encountering the first element smaller than or equal to the pivot.
If scanning indices i and j have not crossed (i < j), we simply exchange A[i] and A[j ] and resume the scans by incrementing i and decrementing j
If the scanning indices have crossed over (i > j), we will have partitioned the subarray after exchanging the pivot with A[j ]
If the scanning indices stop while pointing to the same element (i = j), we have the
subarray partitioned, with the split position s = i = j
We can combine this case with the case of crossed-over indices (i > j ) by
exchanging the pivot with A[j ] whenever i ≥ j
If all the splits happen in the middle of corresponding subarrays, we will have the best case.
-
-
In the worst case, all the splits will be skewed to the extreme: one of the two subarrays will be empty, and the size of the other will be just 1 less than the size of the subarray being partitioned.
-
-
Better pivot selection methods such as randomized quicksort that uses a random element or the median-of-three method that uses the median of the leftmost, rightmost, and the middle element of the array.
switching to insertion sort on very small subarrays (between 5 and 15) or not sorting small subarrays at all and finishing the algorithm with insertion sort applied to the entire nearly sorted array.
Modifications of the partitioning algorithm such as the three-way partition into segments smaller than, equal to, and larger than the pivot
It's worth stopping the scans
after encountering an element equal to the pivot because doing this tends to yield more even splits for arrays with a lot of duplicates, which makes the algorithm run faster.
-