works?

It works by selecting an element from input array called 'pivot' and partition the array into two parts such a way that elements lesser than to pivot will be moved to one side of pivot and greater than pivot to the other side. By doing this, pivot element chosen is aligned to its position where it should belong when the array is sorted. The sub-arrays are then sorted recursively.

There are several ways of selecting a pivot.

• Selecting the first element from the array as pivot.
If the input array is already sorted, then selecting left most element as pivot will give worst-case time complexity, which is O( n²)
• Selecting the last element from the array as pivot.
• Selecting median indexed element from the array as pivot.
This is most commonly used pivot selection, it gives better estimate of the optimal pivot even if the ordering of input array is unknown.
• Selecting any random element from the array as pivot.

Complexity analysis:

To sort an array of n elements, Quicksort algorithm runs in O (n log n) time in average case, but in the worst case it takes O (n²) time. Since this is an in-place algorithm, it takes O(1) constant space. Choice of selecting the pivot element is the key, and a bad choice of pivot can degrade the performance of the algorithm.

Lomuto's

In Lomuto partition scheme, last element in the array is typically chosen as pivot and partition the array such a way that, place smaller than pivot elements on one side of the array and greater than pivot elements to the other side of the array and finally place the pivot in the position where it should be when the array is fully sorted.

Steps involved in this implementation are...

1. Pick right most element from array as pivot.
2. Initialize two variables leftIndex and storeIndex with left index of the array, leftIndex will be used to to iterate over the array and storeIndex will be used to keep track of where in the array smaller or greater than to pivot elements are occurred and swap them with leftIndex element.
3. At the end of loop, storeIndex element and pivot element.
4. Now, we can conclude that pivot is positioned correctly where it should if the array is fully sorted and elements on one side smaller than pivot and elements on other side are greater than pivot.
5. We will have to repeat above steps on left and right sub arrays with indices [left,.....,pivot-1] and [pivot+1,.....,right] recursively.

package io.cscode.algorithms.sorting; public class QuicksortLomutoPartition { /** * Entry method this sorting algorithm * * @param nums */ public void sortArray(int[] nums) { if(nums == null || nums.length==0 ||nums.length==1) { return; } quickSort(nums,0,nums.length-1); } /** * utility method, that calls partition method and recursively calls left and right sub arrays aplit at pivotIndex * * @param nums input array * @param left left index * @param right right index */ private void quickSort(int nums[], int left, int right) { if (left < right) { int partition = partition(nums, left, right); quickSort(nums, left, partition-1); quickSort(nums, partition+1, right); } } /** * select the 'pivot' element and move elements which are lesser than pivot to left side of pivot * and greater than pivot to right side of pivot. * By the end of this, pivot is positioned in its position where it should be after array is sorted. * * @param nums * @param left * @param right * @return pivot index where it is finally positioned */ private int partition(int nums[], int left, int right) { int pivot = nums[right]; int storeIndex = left; for (int leftIndex = left; leftIndex < right; leftIndex++) { if (nums[leftIndex] <= pivot) { swap(nums, leftIndex, storeIndex); storeIndex++; } } swap(nums, storeIndex, right); //at the end move pivot element (right indexed element) to its position to complete the partitioning. return storeIndex; } /** * Utility method to swap elements * * @param nums input array * @param i index to be swapped with j * @param j index to be swapped with i */ private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }

Quicksort implementation using Lomuto partition scheme can be found at GitHub link for Java code and JUnit tests can be found at GitHub link for Unit tests code

Hoare's

Hoare's partition scheme uses two pointers, one pointer starts on left end of the array and the other starts on the right end of of the array, then move these two pointers toward each other until they detect an inversion, meaning that an element on one end pointer is less than pivot and and element on the other end pointer is greater than pivot; When this inversion occurred, if the index first pointer is less than second pointer then these elements should be swapped and continue the process, at some point these pointers cross each other, then we have found a valid partition and return that as partition index and repeat these steps on the sub arrays.

Steps involved in this implementation

1. Pick median element as pivot with (left + right)/2 index, to avoid integer overflow we can change this to left + (right-left)/2.
2. Initialize two variables i = left - 1; and j = right + 1; that we are going to use to iterate from left end of array and right end of array respectively.
3. Within a while infinite loop, do incrementing variable i as long as i^th index element is less than 'pivot' and do decrementing variable j as long as j^th index element is greater than 'pivot'.

Note: Note that we are using do..... while loop to decrement or increment variables i and j because once the while condition is met to break the loop, we need to continue with other elements in the array as well until these pointers cross each other.

4. When a pair of numbers found, i^th and j^th indexes that are less than pivot and greater than pivot, if i is less than j then swap these two element to move 'less than pivot' elements to left side of the array and move 'greater than pivot' elements to right side.
5. When i and j cross each other, then return that index as partition index.
6. Repeat above steps for sub arrays, [left,.....,pivot] and [pivot=1,.....,right]

Note: Notice that in the sub arrays, we are including pivot as well as pivot may not be in its final position when the partition index is found.

package io.cscode.algorithms.sorting; public class QuicksortHoarePartition { /** * Entry method this sorting algorithm * * @param nums input array */ public void sortArray(int[] nums) { if(nums == null || nums.length==0 ||nums.length==1) { return; } quickSort(nums, 0, nums.length-1); } /** * utility method, that calls partition method and recursively calls left and right sub arrays aplit at pivotIndex * * @param nums input array * @param left left index * @param right right index */ private void quickSort(int[] nums, int left, int right) { if(left < right) { int pivotIndex = partition(nums, left, right); quickSort(nums, left, pivotIndex); quickSort(nums, pivotIndex +1, right); } } /** * select the 'pivot' element and move elements which are lesser than pivot to left side of pivot * and greater than pivot to right side of pivot. * By the end of this, pivot is positioned in its position where it should be after array is sorted. * * @param nums * @param left * @param right * @return pivot index where it is finally positioned */ private int partition(int[] nums, int left, int right) { int pivotIndex = left + (right-left)/2; int pivot = nums[pivotIndex]; int i = left-1; int j = right+1; while (true) { do { i++; } while(nums[i] < pivot); do { j--; } while (nums[j] > pivot); if(i >= j) { return j; } swap(nums, i, j); } } /** * Utility method to swap elements * * @param nums input array * @param i index to be swapped with j * @param j index to be swapped with i */ private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }

QuickSort implementation using Hoare's partition scheme source code can be found at GitHub link for Java code and JUnit tests can be found at GitHub link for Unit tests code