Sorting Exercises

1. What is a visualization that you have found to be helpful?
2. Exchange Sorting Algorithms
   1. Discuss with your neighbor(s) how the following sorting algorithms work:
      1. Insertion sort
      2. Bubble sort
      3. Selection sort
   2. Trace the following algorithms sorting the following array:

      6

      4

      10

      2

      8

      0

      Write the contents of the array according to each specified criterion.
      For swaps, put a star above the number(s) that are swapped.
      1. Insertion sort (at the end of each iteration of the outer loop)
      2. Bubble sort (after each swap)
      3. Selection sort (after each swap)
   3. Write down the major steps for the following sorting algorithms:
      1. Insertion sort
      2. Bubble sort
      3. Selection sort
   4. Write down the following properties for the stated sorting algorithms:

      	Best-case   Big-Oh	Average-case   Big-Oh	Worst-case   Big-Oh	Stable?	Extra     Space	Distinguishing     Features
      Insertion Sort
      Bubble Sort
      Selection Sort

3. Discuss with your neighbor(s) how the following sorting algorithms work:
   1. Mergesort
   2. Quicksort
   3. Heapsort
4. How are each of the following animations wrong / inaccurate (compared the videos)?
   1. Mergesort
   2. Quicksort
   3. Heapsort
5. Trace the following algorithms sorting the following array:

   6

   4

   10

   2

   8

   0

   Write the contents of the array according to each specified criterion. For swaps, put a star above the number(s) that are swapped.
   1. Mergesort (at the end of each merge)
   2. Quicksort (after each swap, including swapping the same element in the same place and the swap for the pivot) (choose the pivot as described in the video)
   3. Heapsort (at the end of each iteration of each loop)
6. For the two recursive sorting algorithms in the previous problem (Mergesort and Quicksort), trace the method calls and their parameters as was done in the videos for the same array as above (including indenting to indicate the call stack level).
7. Write down the following properties for the stated sorting algorithms:

   	Best-case   Big-Oh	Average-case   Big-Oh	Worst-case   Big-Oh	Stable?	Extra     Space	Distinguishing     Features
   Mergesort
   Quicksort
   Heapsort

8. Discuss with your neighbor(s) how the following sorting algorithms work:
   1. Bucket sort
   2. Radix sort
9. Trace the following algorithms sorting the following array:

   2152

   3180

   725

   1781

   1248

   4590

   2990

   633

   Write the contents of the array according to each specified criterion.
   1. Bucket sort (show the buckets)
   2. Radix sort (at the end of each iteration)
10. Write down the following properties for the stated sorting algorithms:

    	Best-case   Big-Oh	Average-case   Big-Oh	Worst-case   Big-Oh	Stable?	Extra     Space	Distinguishing     Features
    Bin sort
    Radix sort

Last Modified: