Search

Quicksort

Quicksort is a unstable comparison sort algorithm with mediocre performance. Quicksort uses the partitioning method and can perform, at best and on average, at O(n log (n)). It can, however, perform at O(n2) in the worst case, making it a mediocre performing algorithm.

Table of contents

Performance

Best
Ω(n log(n))
Average
Θ(n log(n))
Worst
O(n2)

Code

public class QuickSort {
    public static void main(String[] args)
    {
        int[]     array  = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
        QuickSort sorter = new QuickSort();
        sorter.quickSort(array, 0, array.length - 1);
        System.out.println(java.util.Arrays.toString(array));
    }

    private void quickSort(int[] array, int startIndex, int endIndex)
    {
        // verify that the start and end index have not overlapped
        if (startIndex < endIndex)
        {
            // calculate the pivotIndex
            int pivotIndex = partition(array, startIndex, endIndex);
            // sort the left sub-array
            quickSort(array, startIndex, pivotIndex);
            // sort the right sub-array
            quickSort(array, pivotIndex + 1, endIndex);
        }
    }

    private int partition(int[] array, int startIndex, int endIndex)
    {
        int pivotIndex = (startIndex + endIndex) / 2;
        int pivotValue = array[pivotIndex];
        startIndex--;
        endIndex++;

        while (true)
        {
            // start at the FIRST index of the sub-array and increment
            // FORWARD until we find a value that is > pivotValue
            do startIndex++; while (array[startIndex] < pivotValue);

            // start at the LAST index of the sub-array and increment
            // BACKWARD until we find a value that is < pivotValue
            do endIndex--; while (array[endIndex] > pivotValue);

            if (startIndex >= endIndex) return endIndex;

            // swap values at the startIndex and endIndex
            int temp = array[startIndex];
            array[startIndex] = array[endIndex];
            array[endIndex] = temp;
        }
    }
}
public class QuicksortGeneric<T extends Comparable<? super T>> {
    public static void main(String[] args)
    {
        // example using Strings
        String[]                     arrayOfStrings = {"Andree", "Leana", "Faviola", "Loyce", "Quincy", "Milo", "Jamila", "Toccara", "Nelda", "Blair", "Ernestine", "Chara", "Kareen", "Monty", "Rene", "Cami", "Winifred", "Tara", "Demetrice", "Azucena"};
        QuicksortGeneric<String> stringSorter   = new QuicksortGeneric<>();
        stringSorter.quicksort(arrayOfStrings, 0, arrayOfStrings.length - 1);
        System.out.println(java.util.Arrays.toString(arrayOfStrings));

        // example using Doubles
        Double[]                     arrayOfDoubles = {0.35, 0.02, 0.36, 0.82, 0.27, 0.49, 0.41, 0.17, 0.30, 0.89, 0.37, 0.66, 0.82, 0.17, 0.20, 0.96, 0.18, 0.25, 0.37, 0.52};
        QuicksortGeneric<Double> doubleSorter   = new QuicksortGeneric<>();
        doubleSorter.quicksort(arrayOfDoubles, 0, arrayOfDoubles.length - 1);
        System.out.println(java.util.Arrays.toString(arrayOfDoubles));
    }

    private void quicksort(T[] array, int startIndex, int endIndex)
    {
        // verify that the start and end index have not overlapped
        if (startIndex < endIndex)
        {
            // calculate the pivotIndex
            int pivotIndex = partition(array, startIndex, endIndex);
            // sort the left sub-array
            quicksort(array, startIndex, pivotIndex);
            // sort the right sub-array
            quicksort(array, pivotIndex + 1, endIndex);
        }
    }

    private int partition(T[] array, int startIndex, int endIndex)
    {
        int pivotIndex = (startIndex + endIndex) / 2;
        T pivotValue = array[pivotIndex];
        startIndex--;
        endIndex++;

        while (true)
        {
            // start at the FIRST index of the sub-array and increment
            // FORWARD until we find a value that is > pivotValue
            do startIndex++; while (array[startIndex].compareTo(pivotValue) < 0) ;

            // start at the LAST index of the sub-array and increment
            // BACKWARD until we find a value that is < pivotValue
            do endIndex--; while (array[endIndex].compareTo(pivotValue) > 0) ;

            if (startIndex >= endIndex) return endIndex;

            // swap values at the startIndex and endIndex
            T temp = array[startIndex];
            array[startIndex] = array[endIndex];
            array[endIndex] = temp;
        }
    }
}
#include <vector>
#include <iostream>

static int partition(std::vector<int> &arr, int startIndex, int endIndex) {
    int pivotIndex = (startIndex + endIndex) / 2;
    int pivotValue = arr[pivotIndex];

    while (true) {
        // start at the FIRST index of the sub-arr and increment
        // FORWARD until we find a value that is > pivotValue
        while (arr[startIndex] < pivotValue) {
            startIndex++;
        }

        // start at the LAST index of the sub-arr and increment
        // BACKWARD until we find a value that is < pivotValue
        while (arr[endIndex] > pivotValue) {
            endIndex--;
        }

        if (startIndex >= endIndex) {
            return endIndex;
        }

        // swap values at the startIndex and endIndex
        int temp = arr[startIndex];
        arr[startIndex] = arr[endIndex];
        arr[endIndex] = temp;
    }
}

void quickSort(std::vector<int> &arr, int startIndex, int endIndex) {
    // verify that the start and end index have not overlapped
    if (startIndex < endIndex) {
        // calculate the pivotIndex
        int pivotIndex = partition(arr, startIndex, endIndex);
        // sort the left sub-arr
        quickSort(arr, startIndex, pivotIndex);
        // sort the right sub-arr
        quickSort(arr, pivotIndex + 1, endIndex);
    }
}

int main() {
    std::vector<int> arr = {12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8};
    quickSort(arr, 0, static_cast<int>(arr.size() - 1));
    for (int i; i < arr.size(); i++) {
        std::cout << arr[i];
        if (i < arr.size() - 1) std::cout << ", ";
    }
}
func quickSort(array: inout [Int], startIndex: Int, endIndex: Int)
{
    // verify that the start and end index have not overlapped
    if (startIndex < endIndex)
    {
        // calculate the pivotIndex
        pivotIndex: Int = partition(array, startIndex, endIndex);
        // sort the left sub-array
        quickSort(array, startIndex, pivotIndex);
        // sort the right sub-array
        quickSort(array, pivotIndex + 1, endIndex);
    }
}

func partition(array: inout [Int], startIndex: Int, endIndex: Int) -> Integer
{
    pivotIndex: Int = (startIndex + endIndex) / 2;
    pivotValue: Int = array[pivotIndex];
    startIndex-=1;
    endIndex+=1;

    while (true)
    {
        // start at the FIRST index of the sub-array and increment
        // FORWARD until we find a value that is > pivotValue
        do startIndex+=1; while (array[startIndex] < pivotValue);

        // start at the LAST index of the sub-array and increment
        // BACKWARD until we find a value that is < pivotValue
        do endIndex-=1; while (array[endIndex] > pivotValue);

        if (startIndex >= endIndex) return endIndex;

        // swap values at the startIndex and endIndex
        int temp = array[startIndex];
        array[startIndex] = array[endIndex];
        array[endIndex] = temp;
    }
}

var array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
insertionSort(array: &array)
print(array)
function quickSort(array, startIndex, endIndex) {
  // verify that the start and end index have not overlapped
  if (startIndex < endIndex) {
    // calculate the pivotIndex
    let pivotIndex = partition(array, startIndex, endIndex)
    // sort the left sub-array
    quickSort(array, startIndex, pivotIndex)
    // sort the right sub-array
    quickSort(array, pivotIndex + 1, endIndex)
  }
}

function partition(array, startIndex, endIndex) {
  let pivotIndex = Math.floor((startIndex + endIndex) / 2)
  let pivotValue = array[pivotIndex]

  while (true) {
    // start at the FIRST index of the sub-array and increment
    // FORWARD until we find a value that is > pivotValue
    while (array[startIndex] < pivotValue) {
      startIndex++
    }

    // start at the LAST index of the sub-array and increment
    // BACKWARD until we find a value that is < pivotValue
    while (array[endIndex] > pivotValue) {
      endIndex--
    }

    if (startIndex >= endIndex) return endIndex

    // swap values at the startIndex and endIndex
    let temp = array[startIndex]
    array[startIndex] = array[endIndex]
    array[endIndex] = temp
  }
}

let array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
quickSort(array, 0, array.length - 1)
alert(array)
def quickSort(array, startIndex, endIndex):
    # verify that the start and end index have not overlapped
    if (startIndex < endIndex):
        # calculate the pivotIndex
        pivotIndex = partition(array, startIndex, endIndex)
        # sort the left sub-array
        quickSort(array, startIndex, pivotIndex)
        # sort the right sub-array
        quickSort(array, pivotIndex + 1, endIndex)

def partition(array, startIndex, endIndex):
    pivotIndex = (startIndex + endIndex) / 2
    pivotValue = array[int(pivotIndex)]

    while (True):

        # start at the FIRST index of the sub-array and increment
        # FORWARD until we find a value that is > pivotValue
        while (array[startIndex] < pivotValue): startIndex += 1

        # start at the LAST index of the sub-array and increment
        # BACKWARD until we find a value that is < pivotValue
        while (array[endIndex] > pivotValue): endIndex -= 1

        if (startIndex >= endIndex): return endIndex

        # swap values at the startIndex and endIndex
        temp = array[startIndex]
        array[startIndex] = array[endIndex]
        array[endIndex] = temp

if __name__ == '__main__':
    array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
    quickSort(array, 0, len(array) - 1)
    print(array)

Walkthrough

Quicksort is a divide and conquer recursive algorithm. The algorithm picks an index typically referred to as the pivot and divides the array into two sub-arrays above and below the pivot. Each sub-array is recursively passed into the quickSort() function.

Partition

The partition() function does all of the work. This function requires 3 parameters: the original array, the starting index of the sub-array, and the end index of the sub-array. The partition() function follows these steps:

  1. Set the pivotValue to equal the index of the array located at (startIndex + endIndex) / 2.
  2. Starting from the startIndex, increment the startIndex forward until we find a value that is greater than the pivotValue.
  3. Starting from the endIndex, decrement the endIndex backward until we find a value that is less than the pivotValue.
  4. If the startIndex is greater than or equal to the endIndex, then return the endIndex.
  5. If step 4 is not true, then swap the values at the startIndex and endIndex and restart the while-loop.

Discussion