CS 2401 Assignment #6

Due Date:
  1. for Part 1, Thursday, October 20 or Monday, October 24, 2011, depending on the day of your lab;
  2. for Part 2, Thursday, October 27 or Monday, October 31, 2011, depending on the day of your lab.

Objective: The goal of this assignment is to practice sorting.

Assignment: Implement the following sorting methods described in the book:

  1. selection sort, bubble sort, and insertion sort (Part 1);
  2. mergesort and quicksort (Part 2).

A. For each of these five methods,

A reasonable way to write a pedagogical implementation is to write an auxiliary method that displays all the elements of the array and waits for the user's reaction; then, every time you change an element of the array while sorting it, you call this auxiliary method.

B. Use techniques described in Assignment 3 to record the computation time needed for each sorting method; for sizes n = 100, 200, 300, and 400 run each several times (e.g., 100) with a randomly generated array and record, for each of the methods, how the average running time grows as a function of n. Explain, to the TA, how the dependence of running time on the array size compares with the estimates of the running time given in the book.