Sorting Exercises

   < Previous  Next >
For your each sorting algorithm:
  1. Insertion sort
  2. Heapsort
  3. Mergesort
  4. Quicksort
  5. Bucket sort
  6. Radix sort
do the following:
  1. Describe how the algorithm works
  2. Trace the following algorithms sorting the following array:
      2152     3180     725     1781     1248     4590     2990     633  
    by writing the contents of the array according to the specified criterion:
    1. Insertion sort (at the end of each iteration of the outer loop)
    2. Heapsort (at the end of each iteration of each loop)
    3. Mergesort (at the end of each merge)
    4. Quicksort (after each swap, including swapping the same element in the same place and the swap for the pivot)
    5. Bucket sort (show the buckets)
    6. Radix sort (at the end of each iteration)
  3. Write down the following properties for the stated sorting algorithms:
      Average-case  
      Running Time      		   Worst-case  
      Running Time      		   Stable?     Extra  
      Space      		   Distinguishing  
      Features  
    Insertion Sort          
    Heapsort          
    Mergesort          
    Quicksort          
    Bucket sort          
    Radix sort          

Last Modified: