Created by shadow.waker
over 10 years ago
|
||
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
Want to create your own Notes for free with GoConqr? Learn more.