CS 2420 Sorting

Sorting Algorithms1. Bubble Sort O(n^2)2. Insertion O(n^2)3. Selection O(n^2)4. Quick O(nlogn)5. Shell O^1.25 - ?6. Merge Sort O(nlogn)7. Heap Sort O(nlogn)8. Radix Sort O(Nk)9. Tree Sort O(nlogn)?10. Pigeon Hole Sort O(n)

Bubble Sort[7][5][1][8][4][6][9][2][3]  n 5  1  7  4  6  8  2  3  9  n-1 1  5  4  6  7  2  3  8  9  n-2 1  4  5  6  2  3  7  8  9    | 1  4  5  2  3  6  7  8  9    | 1  4  2  3  5  6  7  8  9    | 1  2  3  4  5  6  7  8  9   17 times! (1 to make sure)

Insertion Sort[7][5][2][1][8][4][6]  n 5  7  2  1  8  4  6   n-12  5  7  1  8  4  6   n-21  2  5  7  8  4  6     | 1  2  5  7  8  4  6     | 1  2  4  5  7  8  6     | 1  2  4  5  6  7  8    1Looks like Bubble SortLooks at each set as "In Order" Saves each number and inserts it into the "sorted array"

Selection Sort[7][5][2][1][8][6][3]  n                3      8  n-1 6                 7      n-2 3             6            |     1     5                | 2      3                   | 1  2                      1Shows swaps with large/last

Quick Sort[5][10][15][8][25][20][6][12][4][19]Picks any number called "Pivote"20 as pivote:[5][10][15][8][6][12][4][19][20][25]12 as initial pivote:[5][10][8][6][4][12][15][25][20][19]Pivote will come from both sidesEasiest way to pick pivote is start with A[0], then repeat for both sides.

Shell Sort[10][2][5][6][3][8][15][12][4][7][20]Confusing... Need to research

Radix Sort O(nk)  k is size of key. N is size of data321325430215816725200125233444Looks at last number and sorts by that. Then compares second number and so on.

Sorting