http://www.programcreek.com/2012/11/quicksort-array-in-java/
http://www.algolist.net/Algorithms/Sorting/Quicksort
http://www.java2novice.com/java-sorting-algorithms/quick-sort/
http://www.vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html
Iterative Quick Sort
Recursive Version: that uses last element as pivot
- Select a pivot, normally the middle one
- From both ends, swap elements and make left elements < pivot and all right > pivot
- Recursively sort left part and right part
http://www.algolist.net/Algorithms/Sorting/Quicksort
public static void sort(Comparable[] a) { StdRandom.shuffle(a); sort(a, 0, a.length - 1); assert isSorted(a); } // quicksort the subarray from a[lo] to a[hi] private static void sort(Comparable[] a, int lo, int hi) { if (hi <= lo) return; int j = partition(a, lo, hi); sort(a, lo, j-1); sort(a, j+1, hi); assert isSorted(a, lo, hi); } // partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi] // and return the index j. private static int partition(Comparable[] a, int lo, int hi) { int i = lo; int j = hi + 1; Comparable v = a[lo]; while (true) { // find item on lo to swap while (less(a[++i], v)) if (i == hi) break; // find item on hi to swap while (less(v, a[--j])) if (j == lo) break; // redundant since a[lo] acts as sentinel // check if pointers cross if (i >= j) break; exch(a, i, j); } // put partitioning item v at a[j] exch(a, lo, j); // now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi] return j; } public static Comparable select(Comparable[] a, int k) { if (k < 0 || k >= a.length) { throw new IndexOutOfBoundsException("Selected element out of bounds"); } StdRandom.shuffle(a); int lo = 0, hi = a.length - 1; while (hi > lo) { int i = partition(a, lo, hi); if (i > k) hi = i - 1; else if (i < k) lo = i + 1; else return a[i]; } return a[lo]; }
http://www.java2novice.com/java-sorting-algorithms/quick-sort/
http://www.vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html
private int array[]; private int length; public void sort(int[] inputArr) { if (inputArr == null || inputArr.length == 0) { return; } this.array = inputArr; length = inputArr.length; quickSort(0, length - 1); } private void quickSort(int lowerIndex, int higherIndex) { int i = lowerIndex; int j = higherIndex; // calculate pivot number, I am taking pivot as middle index number int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2]; // Divide into two arrays while (i <= j) { /** * In each iteration, we will identify a number from left side which * is greater then the pivot value, and also we will identify a number * from right side which is less then the pivot value. Once the search * is done, then we exchange both numbers. */ while (array[i] < pivot) { i++; } while (array[j] > pivot) { j--; } if (i <= j) { exchangeNumbers(i, j); //move index to next position on both sides i++; j--; } } // call quickSort() method recursively if (lowerIndex < j) quickSort(lowerIndex, j); if (i < higherIndex) quickSort(i, higherIndex); } private void exchangeNumbers(int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; }Iterative Quick Sort
/* A[] --> Array to be sorted, l --> Starting index, h --> Ending index */void quickSortIterative (int arr[], int l, int h){ // Create an auxiliary stack int stack[ h - l + 1 ]; // initialize top of stack int top = -1; // push initial values of l and h to stack stack[ ++top ] = l; stack[ ++top ] = h; // Keep popping from stack while is not empty while ( top >= 0 ) { // Pop h and l h = stack[ top-- ]; l = stack[ top-- ]; // Set pivot element at its correct position in sorted array int p = partition( arr, l, h ); // If there are elements on left side of pivot, then push left // side to stack if ( p-1 > l ) { stack[ ++top ] = l; stack[ ++top ] = p - 1; } // If there are elements on right side of pivot, then push right // side to stack if ( p+1 < h ) { stack[ ++top ] = p + 1; stack[ ++top ] = h; } }}int partition (int arr[], int l, int h){ int x = arr[h]; int i = (l - 1); for (int j = l; j <= h- 1; j++) { if (arr[j] <= x) { i++; swap (&arr[i], &arr[j]); } } swap (&arr[i + 1], &arr[h]); return (i + 1);}/* A[] --> Array to be sorted, l --> Starting index, h --> Ending index */void quickSort(int A[], int l, int h){ if (l < h) { int p = partition(A, l, h); /* Partitioning index */ quickSort(A, l, p - 1); quickSort(A, p + 1, h); }}
1) The above implementation uses last index as pivot. This causes worst-case behavior on already sorted arrays, which is a commonly occurring case. The problem can be solved by choosing either a random index for the pivot, or choosing the middle index of the partition or choosing the median of the first, middle and last element of the partition for the pivot. (See this for details)
2) To reduce the recursion depth, recur first for the smaller half of the array, and use a tail call to recurse into the other.
3) Insertion sort works better for small subarrays. Insertion sort can be used for invocations on such small arrays (i.e. where the length is less than a threshold t determined experimentally)
When does the worst case of Quicksort occur?
The answer depends on strategy for choosing pivot. In early versions of Quick Sort where leftmost (or rightmost) element is chosen as pivot, the worst occurs in following cases.
1) Array is already sorted in same order.
2) Array is already sorted in reverse order.
3) All elements are same (special case of case 1 and 2)
2) Array is already sorted in reverse order.
3) All elements are same (special case of case 1 and 2)
Since these cases are very common use cases, the problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot. With these modifications, the worst case of Quick sort has less chances to occur, but worst case can still occur if the input array is such that the maximum (or minimum) element is always chosen as pivot.
Read full article from Iterative Quick Sort | GeeksforGeeks