Sorting algorithms Cheat Sheet

by Priyal kumar (pryl) via cheatography.com/66402/cs/16808/

Sorting algorithms and Methods Merge sort

Sorting algorithms Methods function merge_sort(list m)

Bubble sort Exchanging ​ ​ ​ // Base case. A list of zero or one
elements is sorted, by defini​tion.
Heapsort Selection
​ ​ ​ if length of m ≤ 1 then
Insertion sort Insertion
​ ​ ​ ​ ​ ​ ​ ​return m
Introsort Partit​ioning & Selection
​ ​ ​ // Recursive case. First, divide the list
Merge sort Merging into equal-​sized sublists
Patience sorting Insertion & Selection ​ ​ ​ // consisting of the first half and second
Quicksort Partit​ioning half of the list.

Selection sort Selection ​ ​ ​ // This assumes lists start at index 0.

​ ​ ​ var left := empty list
Timsort Insertion & Merging
​ ​ ​ var right := empty list
Unshuffle sort Distri​bution and Merge
​ ​ ​ for each x with index i in m do
​ ​ ​ ​ ​ ​ ​ if i < (length of m)/2 then
Best and Worst Case
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ add x to left
Algorithms Best Case Worst Case ​ ​ ​ ​ ​ ​ ​ else
Bogosort n ∞ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ add x to right
2
Bubble sort n n ​ ​ ​ // Recurs​ively sort both sublists.
2 ​ ​ ​ left := merge_​sor​t(left)
Bucket sort (uniform keys) - n k
​ ​ ​ ​right := merge_​sor​t(r​ight)
Heap sort n log n n log n
​ ​ ​ // Then merge the now-sorted sublists.
Insertion sort n n2
​ ​ ​ ​return merge(​left, right)
Merge sort n log n n log n
Quick sort n log n n2 Bogosort
Selection sort n2 n2 while not isInOrder(deck):
4/3
Shell sort n log n n ​ ​ ​ ​shu​ffl​e(deck)
Spreadsort n n(k/s+d)
Bucket sort
Timsort n n log n
Unshuffle sort n kn function bucketSort(array, n) is
​ ​buckets ← new array of n empty lists
Insertion sort ​ for i = 0 to (lengt​h(a​rra​y)-1) do
​ ​ ​ ​insert array[i] into bucket​s[m​sbi​ts(​‐
function insertionSortR(array A, int n)
arr​ay[i], k)]
​ ​ ​ ​ if n>0
​ for i = 0 to n - 1 do
​ ​ ​ ​ ​ ​ ​ ​ins​ert​ion​Sor​tR(​A,n-1)
​ ​ ​ ​nex​tSo​rt(​buc​ket​s[i]);
​ ​ ​ ​ ​ ​ ​ x ← A[n]
​ ​return the concat​enation of bucket​s[0],
​ ​ ​ ​ ​ ​ ​ j ← n-1
...., bucket​s[n-1]
​ ​ ​ ​ ​ ​ ​ ​while j >= 0 and A[j] > x
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​A[j+1] ← A[j]
Resources
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ j ← j-1
​ ​ ​ ​ ​ ​ ​ end while https:​//e​n.w​iki​ped​ia.o​rg​/wi​ki/​Sor​tin​g_a​lgo​rit​hm#​Com​par​iso​n_o​f_a​lgo​‐
​ ​ ​ ​ ​ ​ ​ ​A[j+1] ← x rithms

​ ​ ​ ​ end if http:/​/bi​goc​hea​tsh​eet.com
end function

By Priyal kumar (pryl) Published 27th August, 2018. Sponsored by CrosswordCheats.com

cheatography.com/pryl/ Last updated 27th August, 2018. Learn to solve cryptic crosswords!
priyal-kumar.blogspot.com/ Page 1 of 2. http://crosswordcheats.com
 Sorting algorithms Cheat Sheet
by Priyal kumar (pryl) via cheatography.com/66402/cs/16808/

Sorting algorithm comple​xities Bubble sort (cont)

Algorithms Average Case Memory > end procedure

complexity
Bitonic sorter log 2 n n log2 n Quicksort

Bogosort n × n! 1 algorithm quicksort(A, lo, hi) is

Bubble sort n2 1 ​ ​ ​ if lo < hi then

​ ​ ​ ​ ​ ​ ​ p := partit​ion(A, lo, hi)
Bucket sort (uniform n+k nk
​ ​ ​ ​ ​ ​ ​ ​qui​cks​ort(A, lo, p - 1 )
keys)
​ ​ ​ ​ ​ ​ ​ ​qui​cks​ort(A, p + 1, hi)
Burstsort n(k/d) n(k/d)
algorithm partit​ion(A, lo, hi) is
Counting sort n+r n+r
​ ​ ​ ​pivot := A[hi]
Heap sort n log n 1 ​ ​ ​ i := lo
2
Insertion sort n 1 ​ ​ ​ for j := lo to hi - 1 do
Introsort n log n log n ​ ​ ​ ​ ​ ​ ​ if A[j] < pivot then
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ swap A[i] with A[j]
LSD Radix Sort n(k/d) n+2 d
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ i := i + 1
Merge sort n log n n
​ ​ ​ swap A[i] with A[hi]
MSD Radix Sort (in- n(k/d) 2d
​ ​ ​ ​return i
place)
Patience sort - n Selection sort
k k
Pigeonhole sort n+2 2
procedure selection sort
Quicksort n log n log n ​ ​ list : array of items
Selection sort n2 1 ​ ​ n : size of list
Shell sort Depends on gap 1 ​ ​ for i = 1 to n - 1
sequence ​ ​ /
set current element as minimum /

Spaghetti sort n n2 ​ ​ ​ ​ ​ min = i

​
Spreadsort n(k/d) (k/d)2d
​ ​ ​ ​ check
​ / the element to be minimum /
Stooge sort n(log 3/log1.5) n
​ ​ ​ ​ ​ for j = i+1 to n
Timsort n log n n ​ ​ ​ ​ ​ ​ ​ ​ if list[j] < list[min] then
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ min = j;
Bubble sort
​ ​ ​ ​ ​ ​ ​ ​ end if
procedure bubbleSort( A : list of sortable items ) ​ ​ ​ ​ ​ end for
​ ​ ​ n = length(A) ​ ​ ​ ​ swap
​ / the minimum element with the current
​ ​ ​ ​repeat element/
​ ​ ​ ​ ​ ​ ​ ​swapped = false ​ ​ ​ ​ ​ if indexMin != i then
​ ​ ​ ​ ​ ​ ​ for i = 1 to n-1 inclusive do ​ ​ ​ ​ ​ ​ ​ ​ swap list[min] and list[i]
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ if A[i-1] > A[i] then ​ ​ ​ ​ ​ end if
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​swa​p(A​[i-1], ​ ​ end for
A[i])
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​swapped = true end procedure
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ end if
​ ​ ​ ​ ​ ​ ​ end for
​ ​ ​ ​ ​ ​ ​ n = n - 1
​ ​ ​ ​until not swapped

By Priyal kumar (pryl) Published 27th August, 2018. Sponsored by CrosswordCheats.com

cheatography.com/pryl/ Last updated 27th August, 2018. Learn to solve cryptic crosswords!
priyal-kumar.blogspot.com/ Page 2 of 2. http://crosswordcheats.com