Quick Sort

Quick Sort#

https://en.wikipedia.org/wiki/Quicksort

Contents#

Introduction#

  • Tony Hoare 1961

  • most implementations of quicksort are not stable

complexity

  • \(\Theta(\log n)\) storage is required for the recursive callback but otherwise can be performed without an auxiliary array

  • \(\Theta(n^2)\) worst-case time complexity

  • the performance of quicksort is heavily dependent on the pivot selected and so has an expected time complexity of \(\Theta(n \log n)\)

Divide (quicksort uses a value-partitioning scheme, as opposed to mergesort which uses a size-based/index-based partitioning scheme)

  • select an arbitrary element to serve as the pivot

  • partition the array into sub arrays based on the value of the pivot: elements are swapped such that elements smaller than the pivot appear before it and elements larger than the pivot appear after it (elements equal to the pivot can go on either side)

  • partition(A, start, end) is an in-place operation defined to select a pivot value from the part of the array between the start and end indexes, perform the swapping, and return the index of the final location of the pivot element (the pivot is left in its final sorted position)

Conquer

  • recursively sort the two sub arrays: the two operations of pivot selection and partitioning are recursively applied until the array being processed is a single element

Combine

  • NOT REQUIRED, since once this operation has been recursively applied to each element in the array it will be in sorted order

Merge sort vs quick sort

  • mergesort requires more auxiliary space than quicksort (there are versions of mergesort that require no auxiliary array but these versions perform the worst in practice if not asymptotically)

  • mergesort has better worst-case time complexity than quicksort

  • quicksort performs as good as mergesort in expectation

  • quicksort usually performs better in practice because the constants associated with its time complexity are lower

Algorithm#

 INPUT    an array A[0:n - 1], the index of the first element of A, the index of the last element of A
OUTPUT    nothing (in-place)

QUICKSORT (A, stt, end)
1    if stt == end
2        return A[stt]    // the single-element array A[stt]
3
4    pvt = partition(A, stt, end)
5
6    QUICKSORT(A, stt, pvt - 1)
7    QUICKSORT(A, pvt + 1, end)

 INPUT    an array A, the index of the first element of A, the index of the last element of A
OUTPUT    the index of the pivot element

partition (A, stt, end)
 1    pvt = choose_pivot(A, stt, end) // select a pivot element and return its index
 2
 3    swap(A[pvt], A[end])            // swap the pivot element to the end of the array
 4
 5    j = stt
 6    for i = stt to end - 1
 7        if A[i] <= A[pvt]
 8            swap(A[j], A[i])
 9            j++
10
11    swap(A[j], A[end])   // index j is pointing to the first element larger than the pivot element, so swap them
12
13    return j             // return the index of the pivot element

choose_pivot

There are different ways of going about selecting a pivot element. One can select the first element as the pivot element; the last element; a random element; the middle element; or some other approach.

partition

Start from the leftmost element and track the index of elements that are less than or equal to the pivot element.

Example

   i|
A = 5 3 1 6 4 9 11 2, stt = 0, end = 7
   j|

      |
A = 5 3 1 6 4 9 11 2, stt = 0, end = 7
    |

        |
A = 5 3 1 6 4 9 11 2, stt = 0, end = 7
    |

          |
A = 1 3 5 6 4 9 11 2, stt = 0, end = 7
      |

...

                 |
A = 1 2 5 6 4 9 11 3, stt = 0, end = 7
      |

Complexity#

Since quicksort is a divide and conquer algorithm we can analyze its time complexity in those terms. The combination component of quicksort is the partition operation which runs in linear time, and there are two subproblems per recursion.

\(T(n) = 2T(\cdot) + \Theta(n)\)

In the best case, the pivot is selected so as to divide the array in half. This yields two sub problems of size \(n/2\).

\(\text{best}\quad T(n) = 2T(n/2) + \Theta(n)\)

In the worst case, either the smallest element or the largest element is selected. This yields one sub problem of size \(0\) and another sub problem of size \(n - 1\).

\(\text{worst}\quad T(n) = T(n - 1) + \Theta(n) = \Theta(n^2)\)

This analysis shows why how the pivot element is selected is significant. If the pivot element is selected at random then selecting the worst-case pivot element every time is unlikely. The expected-case complexity is

\(\text{expected}\quad T(n) = \Theta(n \log n)\)

Quicksort sorts in-place, which means that no auxiliary array is required and so the space cost is just a function of the depth of the call stack.

In the balanced case

\(S(n) = S(n/2) + \Theta(1) = \Theta(\log n)\)

In the worst case

\(S(n) = S(n - 1) + \Theta(1) = \Theta(n)\)

There are optimizations to ensure that even in the worst case \(\Theta(\log n)\) space is all that is required. In practice then the worst-case space complexity of quicksort is usually stated as logarithmic as well.

Implementations#

C#

/*    sort_quick_last.c (QUICKSORT)
 *
 *    this implementation of quick sort does not use any fancy pivot selection operation
 *    rather it just selects the last element of the array as the pivot element
 */

#include <stdio.h> // printf


/**************************************************
 *
 *          auxiliary
 *
 **************************************************/
void print_arr (int A[], int n, char *str) {
  printf("%s: ", str);
  for (int i = 0; i < n; i++)
    printf("%d ", A[i]);
  printf("\n");
}

void swap (int *a, int *b) {
  int t = *a;
     *a = *b;
     *b =  t;
}


/**************************************************
 *
 *          QUICKSORT
 *
 **************************************************/
int partition (int A[], int stt, int stp) {
  int pvt = stp;          // select the last elem as the pivot elem
  swap(&A[pvt], &A[stp]); // swap the pivot elem to the end of the array (this is redundant in this implementation)

  int j = stt;
  for (int i = stt; i < stp; i++) { // iterate over all elems except the last one, the pivot elem
    if (A[i] <= A[pvt]) { // if        elem i is less than or equal to the pivot elem
      swap(&A[i], &A[j]); // then swap elem i to the lefthand side of the array
      j++;                // and  increment the index of the pivot elem
    }
  }

  // A[j] is the first elem larger than the pivot elem, so swap them
  // the pivot elem is now in its proper position in the array
  swap(&A[j], &A[stp]);

  // return the index of the pivot elem
  return j;
}

void quicksort (int A[], int stt, int stp) {
  /*                     ^^^^^^^           index of the first elem
   *                              ^^^^^^^  index of the last  elem
   */

  // base case
  if (stt >= stp) // if the array consists of a single elem
    return;

  // combine step
  int pvt = partition(A, stt, stp);

  // divide  step
  quicksort(A, stt, pvt - 1);
  quicksort(A, pvt + 1, stp);
}


/**************************************************
 *
 *          driver
 *
 **************************************************/
int main (void) {
  int A[] = {2, 1, 5, 8, 5, 6, 7, 4, 8, 7, 5, 1, 7, 3, 0, 3, 1, 5, 0, 7};
  int   n = sizeof(A) / sizeof(A[0]);

  print_arr(A, n, "       array");
  quicksort(A, 0, n - 1);
  print_arr(A, n, "sorted array");

  return 0;
}

Acknowledgments#

Contents