Exercises
Write a bin sort and radix sort algorithm using linked lists. Compare their runtime with algorithms implemented using lists.
Rewrite the original selection sort algorithm such that redundant swaps (of the same elements) are removed, and also compare its system runtime with the original algorithm.
Out of the following, which algorithm preserves the original ordering of duplicate elements in the input vector? Can you suggest modifications which can prevent redundant swaps from occurring?
Insertion sort
Bubble sort
Selection sort
Shell sort
Merge sort
Quick sort
Heap sort
Bin sort
Radix sort
Can you prove why comparison-based sorting algorithms require a minimum asymptotic complexity of O(nlog n) for worst-case scenarios?
Compare the empirical performance of merge sort using vector-based and linked list based implementation.
