Homework: Sorting Algorithms

   < Previous  Next >
Write your answers to the following questions in a flat text file hwkSorting.txt (not a Word document nor a Rich Text Format file).
  1. Trace the algorithms below sorting the following array:
      78     12     1     55     77     13     14     56  
    1. Insertion sort (at the end of each iteration of the outer loop)
    2. Bubble sort (after each swap)
    3. Heapsort (at the end of each iteration of each loop)
    4. Mergesort (at the end of each merge)
    5. 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)
    6. Radix sort (at the end of each iteration)
    Please put each array on a separate line.
  2. For the two recursive sorting algorithms in the previous problem, trace the method calls and their parameters as was done in the videos (including indenting to indicate the call stack level). (If applicable, you can leave out a method call for choosing a pivot.)
  3. If you perform a simple external sort with 4 tapes (as described in the video) on 11 values with at most x=3 values fitting into main memory at once, how many times do you perform a read, write or rewind of x values to/from a tape? If two tapes are being read or written to simultaneously, count that as one wait. You can assume that all of the read/write heads are rewound to begin with and do not need to be rewound when finished. The values start on tape 1 and need to be back on tape 1 in sorted order. Here are some value to use if you want some concrete numbers: 94, 38, 71, 62, 14, 81, 12, 84, 70, 93, 75.
  4. For the following scenarios, choose the most appropriate sorting algorithm (from those discussed in class) and your justification of why it is the most appropriate:
    1. A large array that is almost already sorted
    2. Large objects (> 1 MB each) with unique keys for every person that is living or has lived.
    3. Your grades for assignments in this class.

Submission

Submit your txt file at https://3110.cs.mtsu.edu/. For further instructions, please see the Miscellaneous page.

Rubric:

Points         Question
------------   --------------------------------------------------------------
_____ / 10.5   1
_____ /  3.0   2
_____ /  3.0   3
_____ /  1.5   4
	       
_____ / 18.0   Total

Last Modified: