R Data Structures and Algorithms

Exercises

1. Write a bin sort and radix sort algorithm using linked lists. Compare their runtime with algorithms implemented using lists.
2. 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.
3. 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
4. Can you prove why comparison-based sorting algorithms require a minimum asymptotic complexity of O(nlog n) for worst-case scenarios?
5. Compare the empirical performance ...