Quick Sort - Java Code

An efficient, not stable, comparison sorting algorithm

• Worst case time complexity: O(n2)      /* rarely occurs */
• Best case time complexity: O(n log n)

Two versions:

• Out-of-place version
• In-place version

Algorithm ( Out-of-place version)

Algorithm quickSort(S)

Input sequence S

Output S in sorted order

if( |S| = 0 or |S| = 1 ) then

    return S

p ← pickPivot()

     

(L,E,G) ← partition(S, p)

     

quickSort( L )

quickSort( G )

return L U E U G

----------------------------------------------------------------------------------------------------------

Algorithm partition(S, p)

                Input: sequence S, position p of pivot

                Output: subsequences L, E, G of the elements of S less than, equal to,

                                or greater than the pivot, respectively

L, E, G ← empty sequences

pivot ← S.removeElementAt(p)

while !S.isEmpty() do

    y ← S.removeFirst()

    if y < pivot then

       L.insertLast(y)

    else if y = pivot then

       E.insertLast(y)

    else

       G.insertLast(y)

return L, E, G

Algorithm ( In-place version)

Algorithm inPlaceQuickSort(S, left, right)

                Input array S, positions left and right

                Output array S with the elements from positions left to right
                                rearranged in increasing order

               

if left > right

return

k ← a random integer between left and right

swap(k, right)  //place pivot at the right

x ← S.elemAtPos( right ) //the pivot

i ← inPlacePartition(x) //new position of pivot

swap(right , i) //place pivot in proper location

inPlaceQuickSort(S, left, i - 1)

inPlaceQuickSort(S, i + 1, right)

------------------------------------------------------------------------------

In Place Partitioning:

1. Move pivot to the far right (pos = r)

2. Begin with pointers i, j with i at pos  l and j at pos r – 1 (for readability, we let l = 0 in this discussion).

3. Move i to the right past all values < pivot

4. Move j to the left past all values > pivot

5. If stuck, then swap the values and repeat 3, 4, allowing i to move one to the right and j to the left when their turns come (equivalently: after swap, immediately increment i and decrement j by 1)

6. Stop as soon as j crosses (moves 1 to the left of) i or i crosses (moves 1 to the right of) j

7. After stopping, swap positions of pivot and value at position i.

Java Code ( Out-of-place version )

public List<Integer> quickSort(List<Integer> arr) {

       if (arr.size() <= 1) {

              return arr;

       }

       int pivot = pickPivot(arr);

       List<Integer> left = new ArrayList<Integer>();

       List<Integer> pivots = new ArrayList<Integer>();

       List<Integer> right = new ArrayList<Integer>();

       partition(arr, pivot, left, pivots, right);

       left = quickSort(left);

       right = quickSort(right);

       List<Integer> finalSorted = new ArrayList<Integer>();

       finalSorted.addAll(left);

       finalSorted.addAll(pivots);

       finalSorted.addAll(right);

       return finalSorted;

}

public void partition(List<Integer> arr, int pivot,

              List<Integer> left, List<Integer> pivots, List<Integer> right) {

       for (int item : arr) {

              if (item < pivot) {

                     left.add(item);

              } else if (item == pivot) {

                     pivots.add(item);

              } else {

                     right.add(item);

              }

       }

}

public int pickPivot(List<Integer> arr) {

       /*

        * "median-of-three" rule. Best pivot is median of first, middle and

        * last element of array

        */

       int middleIndex = arr.size() / 2;

       int first = arr.get(0);

       int middle = arr.get(middleIndex);

       int last = arr.get(arr.size() - 1);

       if ((first - middle) * (last - first) >= 0) {

              return first;

       } else if ((middle - first) * (last - middle) >= 0) {

              return middle;

       } else {

              return last;

       }

}

Java Code ( In-place version )

public void quickSortInPlace(int[] arr) {

       quickSortInPlace(arr, 0, arr.length - 1);

}

private void quickSortInPlace(int[] arr, int lower, int upper) {

       if (lower > upper) {

              return;

       }

       // pick a random integer between lower and upper bound

       int pivotIndex = pivotIndex(arr, lower, upper);

       // place the pivot at the upper index

       swap(arr, pivotIndex, upper);

       int correctPositionOfPivot = inPlacePartition(arr, lower, upper);

       swap(arr, correctPositionOfPivot, upper);

       quickSortInPlace(arr, lower, upper - 1);

       quickSortInPlace(arr, lower + 1, upper);

}

private int inPlacePartition(int[] arr, int lower, int upper) {

       // pivot element is at the upper index

       int pivotIndex = upper;

       int pivot = arr[pivotIndex];

       while (lower <= upper) {

              while (arr[lower] < pivot) {

                     lower++;

              }

              while (arr[upper] > pivot) {

                     upper--;

              }

              if (lower > upper) {

                     swap(arr, lower++, upper++);

              } else {

                     break;

              }

       }

       return lower;

}

public int pivotIndex(int[] arr, int lower, int upper) {

       /*

        * "median-of-three" rule. Best pivot is median of first, middle and

        * last element of array

        */

       int middleIndex = (upper - lower) / 2;

       int left = arr[lower];

       int middle = arr[middleIndex];

       int right = arr[upper];

       if ((left - middle) * (right - left) >= 0) {

              return lower;

       } else if ((middle - left) * (right - middle) >= 0) {

              return middleIndex;

       } else {

              return upper;

       }

}

public void swap(int[] arr, int i, int j) {

       int temp = arr[i];

       arr[i] = arr[j];

       arr[j] = temp;

}