Sorting Algorithms

Front 1

1 Pick an element, called a pivot, from the list.
2 Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3 Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
The base case of the recursion are lists of size zero or one, which never need to be sorted.

Back 1

quicksort

Front 2

1 If the list is of length 0 or 1, then it is already sorted. Otherwise:
2 Divide the unsorted list into two sublists of about half the size.
3 Sort each sublist recursively by re-applying the algorithm
4 Combine the two sublists back into one sorted list

Back 2

merge sort

Front 3

1 build a heap out of the data set
2 remove the largest item and place it at the end of the partially sorted array
3 reconstruct the heap, remove the largest remaining item, and place it in the next open position from the end of the partially sorted array
3 repeat until there are no items left in the heap and the sorted array is full

Back 3

heapsort

Front 4

1 Suppose there exists a function called Insert designed to insert a value into a sorted sequence at the beginning of an array. It operates by beginning at the end of the sequence and shifting each element one place to the right until a suitable position is found for the new element. The function has the side effect of overwriting the value stored immediately after the sorted sequence in the array.
2 begin at the left-most element of the array and invoke Insert to insert each element encountered into its correct position. The ordered sequence into which the element is inserted is stored at the beginning of the array in the set of indices already examined. Each insertion overwrites a single value: the value being inserted.

Back 4

insertion sort

Front 5

1 Find the minimum value in the list
2 Swap it with the value in the first position
3 Repeat the steps above for the remainder of the list (starting at the second position and advancing each time)

Back 5

selection sort

Front 6

1 Chose a increment sequence, which ends with 1
2 Perform the gap insertion sort for each number in the increment sequence, until it finishes with 1

Back 6

shell sort

Front 7

1 compare each pair of adjacent items and swap them if they are in the wrong order.
2 repeat the pass through until no swaps are needed

Back 7

bubble sort

Front 8

1 Set up an array of initially empty containers
2 Scatter: Go over the original array, putting each object in its container.
3 Sort each non-empty container.
4 Gather: Visit the containers in order and put all elements back into the original array.

Back 8

bucket sort

Front 9

1 Take the least significant digit (or group of bits, both being examples of radices) of each key.
2 Group the keys based on that digit, but otherwise keep the original order of keys. (This is what makes the LSD radix sort a stable sort).
3 Repeat the grouping process with each more significant digit.

Back 9

radix sort (LSB)