Quicksort

A type of linearithmic sort Quick sort has a running time of O(n^2) in the worst case, but it is typically O(n lg n).

• A fined tuned implementation beats most sorting algorithms.

The Big Picture

Partition the sequence into two subsequences separated by a single element x that is is greater than or equal to every element to its left sequence and less than equal to elements to its right.

• After the partition, the element $x$, called the pivot element will be in its final (sorted) position.

We now apply the partition to two subsequences separately. This process is naturally recursive (and quick).

Partition

// Partition by taking the right-most element as pivot.  
// Pre: 0 <= left <= right <= arr.length;  
// Post: a[left] <= .. <= pivot <= .. <= a[right - 1]  
// Returns: index of pivot element in array.
private static int partition(int[] arr, int left, int right) {  
  int p = right - 1; // point to pivot  
  int l = left; // left marker  
  int r = p - 1; // right marker  
  
  while (l <= r) {  
    while (arr[l] <= arr[p] && l <= r) {  
      l++; // move l to right as long as condition holds.  
    }  
  
    while (arr[r] >= arr[p] && r >= l) {  
      r--; // move r to left as long as condition holds.  
    }  
  
    if (l < r) {  
      // arr[l] and arr[r] are out of order with respect to pivot  
      swap(arr, l, r);  
    }  
  }  
  
  if (l != p) {  
    // move the pivot to its final place  
    swap(arr, l, p);  
  }  
  
  return l; // return index of item now known to be in place  
}

Quicksort Implementation

// Pre: 0 <= left <= right <= arr.length.  
// Post: arr[left] ... arr[right-1] is sorted.  
private static void quicksort(int[] arr, int left, int right) {  
  if (right - left < 2) {  
    return;  
  }  
  
  int pivot = partition(arr, left, right);  
  quicksort(arr, left, pivot);  
  quicksort(arr, pivot + 1, right);  
}

Analysis

The partition subroutine runtime is O(n) because each element is visited once using the left and right pointers. In the worst case, quicksort runs in O(n^2) in the worst case.

We assume the case where we select the pivot to be the right most elements: The worst case is when the sequence values are already sorted in ascending/descending order.

1. In this case, the partition algorithm will always select the next smallest/largest element, resulting in the most unbalanced split possible; two subsequences with n-1 and 0
2. repeating the partitioning of this type will occur O(n) times before both subsequences get down to 1 or 0 subsequences (base-case)
3. There will be n calls made to the partition algorithm which itself runs in O(n) time.
4. So, the total running time for the quicksort algorithm, in this case, is O(n^2).

• The worst case quicksort behaves like a selection sort because each call to partition amounts to selecting the largest/smallest element from the subsequence passed to it.

The best case is when the sequence values are not in sorted order. Instead, the values are in random order.

1. The recursive call to the quicksort algorithm divides the sequence into two subsequences of n/2 length.
2. Similar to binary search and merge sort, this repeated subdividion takes lg(n) steps to get down to the base case.
3. So there will be O(lgn) subsequences and that many calls to the partition algorithm which runs in O(n) time.

• The total running time for the quicksort algorithm in this case is O(n lg n).

The average case is when the quiucksort runs in O(n lg n) time.

Pivot

We chose the rightmost element as our pivot, but the analysis would be the same if we chose the leftmost element.

If we chose the middle element for the case of the sorted sequence, it would result in the best-case pperformance because it results in partitions of nearly equal length.

• Generally, the ideal pivot is the median of the sequence to be partitioned.

One can calculate the average of all values or the mid-point value as (max+min)/2. However, these strategies are O(n) to compute and only good if the values are in a normal gaussian distribution.

Another strategy is to select a ranndom element as the pivot and hope the choice makes for partitions of nearly equal length. It can be shown this strategy results in expected O(n lg n) worst-case runtime.

A popular choice for pivot is selecting the median of the leftmost, rightmost, and middle elements in the sequence. This strategy is called the median of the three.

Java Sorts

Java's Collections.sort() metho dimplements a variant of the merge sort.

Arrays.sort() implements the quicksort, selecting the pivot as the median of the three elements (first, last, and middle) when n <= 4, and the median of nine equally spaced elmeents when n > 40. It then switches to inesrtion sort when n < 7.

Java uses quicksort to sort a collection (array) of primitives but for collections of reference variables, it uses merge sort because Java API guarantees a stable sorting, which merge sort offers but quicksort doesn't offer. However, whne sorting primitive values by their natural order, you would not notice a difference as primitive values have no identity. Therefore, quicksort can be used for primitive arrays and will be used when it is considered more efficient.

Stable Sorting

Stable sorting algorithm is one where it maintains the order of elements with duplicate values. This property may be necessary if the sort order is based on a subset of attributes in an object.

Sorts that are stable

• bubble as long as it doesn't swap equal values
  • It continueusly compares adjacent items so that the most significant items bubble to the end.
• insertion as long as it doesn't swap equal values
  • continuously and sequentially compares elements and arranges them in a particular order. It can be stable because all identiacal elements are inserted in the sorted array after one another in the same order discovered.
• merge
  • It breaks down the array into multiple subarrays of halved size and builds back up to the original collection via comparison. The sort is stable as long as the same pattern for equivalent items is maintained (e.g., always taking left-half values).

Sorts that are not stable:

• selection
  • it repeatedly finds the min element in the unsorted part of a list and swaps them with the first item. Due to this nature, duplicate items will not remain in the same order.
• heap
  • removes items from the created heap in rank order, so any information about the original ordering of items is lost during the heap creation stage, which came first.
• quicksort
  • it will exchange nonadjacent elements.