Sorting big-Oh for lab 9(Week 11)

Nearly-sorted input

Reverse-sort input

                                                              Randomized input

During our lab9, we did some analyses on sorting. There were 6 sorting methods we discussed. Selection, Insertion, Bubble, Merge , Quicksort, list.sort. We found the average case for Bubble, Insertion and Selection are O(n^2), Merge and quicksort are O(nlogn), list.sort is O(n). In the end, we found list.sort is the most stable in six sorting methods. The 3 graphs above are their runtime trends. The 3 tables below are their runtime details.

Random	100	200	300	400	500	600
Selection	0.00175	0.00448	0.010012	0.01794	0.028137	0.043832
Insertion (1)	0.001457	0.005964	0.012746	0.022136	0.034737	0.0538
Bubble (1)	0.002344	0.009587	0.021157	0.036821	0.060712	0.090284
Merge (1)	0.000748	0.001684	0.00278	0.00365	0.004675	0.00582
Quicksort (1)	0.000528	0.001212	0.002021	0.002537	0.003176	0.004041
list.sort	0.000026	0.00006	0.000098	0.000138	0.000181	0.000222
Sorted	100	200	300	400	500	600
Selection	0.001451	0.004507	0.00984	0.017734	0.02751	0.039828
Insertion (1)	0.000092	0.000109	0.000302	0.000403	0.000491	0.000602
Bubble (1)	0.001308	0.005093	0.011387	0.020254	0.031784	0.046298
Merge (1)	0.000572	0.001217	0.001944	0.002637	0.003372	0.004105
Quicksort (1)	0.000911	0.002744	0.004596	0.006878	0.009558	0.012427
list.sort	0.000027	0.00006	0.0001	0.000139	0.000183	0.000227
Sorted, reversed	100	200	300	400	500	600
Selection	0.001882	0.004683	0.010407	0.018529	0.029347	0.041515
Insertion (1)	0.002878	0.011151	0.024815	0.044362	0.069045	0.10773
Bubble (1)	0.003478	0.013683	0.030688	0.054437	0.087364	0.129299
Merge (1)	0.00645	0.001399	0.002183	0.002965	0.003652	0.004605
Quicksort (1)	0.001841	0.006883	0.015072	0.026561	0.041432	0.059968
list.sort	0.000026	0.00062	0.0001	0.000141	0.000183	0.000224