CSC 241- Assignment 3



Part1-Implement Quick Sort (Due November 21, 2003)

Extend intList to create a new class sortableIntList. This class inherits all methods of intList as they already exist and adds on a new method named sort that uses the quick sort algorithm to sort the list in ascending order.

As you know, quick sort identifies a pivot value from the elements in a list, then, it moves the values smaller than the pivot to its left and the rest of the values to its right. The left and right sublists are then each sorted by applying the same algorithm to them.

In writing the sort method, you will implement quicksort. Unlike the implementation of quicksort for an array where elements get to move within the same array, here, we can create our left and right sublists as sortableIntLists and when moving value to the left of pivot, to us, it would mean that we are adding those elements to the left sublist and, of course, the other values to the right sublist. Here is the basic algorithm that you need to implement for the sort method: