Show Menu
Cheatography

Sorting Algorithms Cheat Sheet (DRAFT) by

All sorting algorithms with pseudocode

This is a draft cheat sheet. It is a work in progress and is not finished yet.

Time

 
Worst Case
Best Case
Average Case
Selection Sort
O(n^2)
O(n^2)
O(n^2)
Insertion Sort
O(n^2)
O(n)
O(n^2)
Merge Sort
O(n logn)
O(n logn)
O(n logn)
Quick Sort
O(n^2)
O(n logn)
O(n logn)
Heap Sort
O(n logn)
O(n)
O(n logn)
Counting Sort
O(n)
O(n)
O(n)
Radix Sort
O(n)
O(n)
O(n)
 

QuickSort

QUICKSORT(A, p, r)
    if p < r
        q = PARTITION(A, p, r)
        QUICKSORT(A, p, q - 1)
        QUICKSORT(A, q + 1, r)

PARTITION(A, p, r)
    x = A[r]
    i = p - 1
    for (p <= j <= r - 1) do
        if (A[j] <= x) then
            i = i + 1
            SWAP (A[i], A[j])
        fi
    od
    SWAP (A[i + 1], A[r])
    return i + 1