CS 2420 Sorting

Page 1

Sorting Algorithms

1. 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 1

7 times! (1 to make sure)

Insertion Sort

[7][5][2][1][8][4][6] n

5 7 2 1 8 4 6 n-1

2 5 7 1 8 4 6 n-2

1 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 1

Looks like Bubble Sort

Looks 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 1

Shows 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 sides

Easiest 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 data

321

325

430

215

816

725

200

125

233

444

Looks at last number and sorts by that. Then compares second number and so on.

Sorting