Date: Tue, 14 Jan 1997 20:29:55 GMT Server: NCSA/1.5 Content-type: text/html No Title

CS 112 - Introduction to Computer Science II
Spring Semester 1995
Homework Number 5

This homework is due on April 13. There is an extra credit exercise which is optional except for honors students.

  1. Consider the following array of integers :

    15, 9, 7, 5, 10, 4, 2, 3, 1

    Write down the array after each iteration (recursive call) of

    1. Quicksort

    2. Merge Sort

  2. (Taken from ``Data Structures Using C'' by Tanenbaum et.al). A sort by counting is performed as follows. Declare and array count and set count[i] to the number of elements that are less than x[i]. Then place x[i] in position count[i] of an output array. (However, beware of the possibilities of equal elements.) Write a routine to sort an array x of size n using this method. Write a program to test your routine.

  3. (Extra credit.) Implement the Quicksort algorithm for two way linked lists.





Alberto Oliart
Sat Apr 8 18:07:10 EDT 1995