Algorithms and Data Structures (INF1, Autumn'05)
Exercise Set 11
Exercise 1:
Suppose that we have an array A[1..n] of n integers such
that every element of the array is in the range from 1 to k
(where k is a given constant).
- Write an algorithm which will sort the array A with
the worst-case time complexity O(n+k). (Hint: use an additional
array B[1..k]).
- Assume now that k < n, which implies that the worst-case
time complexity of your algorithm is O(n). Does this contradict
the Ω(n*log n) lower-bound on sorting? Explain why yes/no.
Exercise 2:
Consider an array A[1..6] such that A[1]=5, A[2]=9, A[3]=2,
A[4]=7, A[5]=2, A[6]=1. Demonstrate on a paper the strategies
when sorting this array using
- insertion sort
- selection sort
- array-based quick sort.
Exercise 3:
Experiment with
this web-page. Try to race several sorting
algorithms against each other on random inputs. Which one is the fastest
one? What conclusions can you draw?