This page is designed as a terse reference for the various sorting algorithms used in this lab. You may observe the sort in action by clicking on the image in the second column of each row. If you find yourself in need of more detail, review your text and course notes.
| Name | Approximate Time Performance on a Data Set of Size n |
Applet | Description | ||
| Best Case | Average Case | Worst Case | |||
| Insertion | n |
n2 |
n2 | A very intuitive yet somewhat slow algorithm. Each element in the collection is removed from its original place and inserted in the correct place. If two elements are equal, the original ordering will be maintained. Insertion sort is order n2 in the worst and average cases, as n-1 elements must be selected and re-inserted and each insertion requires up to n-1 comparisons. | |
| Shell | n |
n1.25 |
n1.5 | Although shell sort is order n 1.5. you may find it useful to know that its average time is n 1.25 and its optimal time is nearly n. | |
| Quick Sort | n log n |
n log n |
n2 | Quick Sort is, on average, one of the fastest sorts. Its divide and conquer approach is extremely efficient for randomly sorted lists, but you may find it interesting that it exhibits very poor performance on sorted and nearly sorted lists. | |
| Bubble | n |
n2 |
n2 | By far the slowest algorithm worth mentioning. Like insertion, selection, and shell sort, bubble sort is order n2. Bubble Sort performs especially poorly on large data sets, while the complexity of sorted sets may be close to n. | |
| Selection | n2 |
n2 |
n2 | Also a very slow n 2 algorithm, the Selection Sort is known to perform approximately 60% better than the bubble sort. However, the insertion sort still outperforms the selection sort by a notable margin. Expect the Selection Sort to perform especially poorly on large data sets. | |
| Heap | n log n |
n log n |
n log n | Of the n log n algorithms listed here, heap sort is the slowest. The heap sort's performance diminishes in comparison to quick and merge sorts as the data set increases in size. | |
| Merge | n log n |
n log n |
n log n | A popular algorithm for its performance. Detecting the comparative advantage of merge sort over heap sort is only discernable with large data sets. | |