Sorting Fun

Sorts

Selection Sort (pg. 425 - 427)

• See it in action @ http://www.youtube.com/watch?v=Ns4TPTC8whw

Bubble Sort (pg. 428 - 431)

• See it in action @ http://www.youtube.com/watch?v=lyZQPjUT5B4

Insertion Sort (pg. 431 - 434)

• See it in action @ http://www.youtube.com/watch?v=ROalU379l3U

Shell Sort (pg. 437 - 440)

• See it in action @ http://www.youtube.com/watch?v=CmPA7zE8mx0

Merge Sort (pg. 441 - 446)

• See it in action @ http://www.youtube.com/watch?v=XaqR3G_NVoo

Heap Sort (pg. 446 - 451)

• See it in action @ http://www.youtube.com/watch?v=6NB0GHY11Iw

Quick Sort (pg. 451 - 459)

• See it in action @ http://www.youtube.com/watch?v=ywWBy6J5gz8

Big O of Number of Comparisons

Sort	Best	Worst	Average
Selection	O(n^2)	O(n^2)	O(n^2)
Bubble	O(n)	O(n^2)	O(n^2)
Insertion	O(n)	O(n^2)	O(n^2)
Shell	O(n^7/6)	O(n^5/4)	O(n^2)
Merge	O(n log n)	O(n log n)	O(n log n)
Heapsort	O(n log n)	O(n log n)	O(n log n)
Quicksort	O(n log n)	O(n log n)	O(n^2)