Discussion in 'C' started by annapink, Apr 1, 2008.

1. ### annapinkNew Member

Joined:
Apr 1, 2008
Messages:
2
0
Trophy Points:
0
Hi, can any of you guys help me with this, i've already done part one but i'm not sure how to do part 2 and part 3.

Many Thanks

Part 1

Lecture 4 contains a description of an algorithm for performing a partition on unsorted data. The partition operation (implemented as a function) is used for performing the quicksort algorithm (described in the notes for lecture 9).

I would like you to read and understand how the partition operation works.

This part of the exercise asks you to make up a set of 12 small integer values (I suggest you make them all different) and apply the rules described in the notes to them. This is a pencil & paper exercise! Do not use the same data as given in the notes!

Part 2

Using the notes from lecture 4, implement and test the partition function. I suggest you apply it to an array of integers.

This assumes you will print out an array of random integer values (which need not be bigger than about 12 values for this exercise) before and after applying the partition function to them.

I would expect the prototype of the partition function to be:

int partition(int numbers[], int size);

where numbers is the array of numbers and size is how many numbers there are. The return value is the array index of the item known as the pivot (where all values on one side of the pivot are less than the pivot and all values to the other side are greater than or equal to the pivot). You should be able to test it against your test data from part 1.

This is a non-trivial programming exercise!

Part 3 (for an extra 2 marks to replace any lost marks from earlier tutorials)

Using the description of the quicksort function described in the notes for this lecture (lecture 9), complete the implementation of the quicksort function. You should be able to make a comparison of the quicksort with the bubble sort. Again, I suggest this is done using integer data (although you could, if you want, extend the student sorting problem to include the quicksort algorithm).