C++Recursion

In this lab, you will write a program to explore the performance of several of the sorting algorithms we have learned. You will observe the performance of various secret implementations and use the results to decide what sorting algorithm is used in each implementation.

The Sorting Algorithms:

The program runs 3 sorting algorithms, Bubble Sort, Selection Sort and Quick Sort. When running one of the algorithms, it tracks the number of comparisons performed, the number of times data items are moved, and the actual time elapsed.

More details on the program and the experimental data it reports:

The program reports the number of comparisons performed. Every time an element in the array is compared to something else (a temporary value, another location in the array), this counts as a comparison.

(Optional) The program reports the number of movements performed. Any instruction that copies or moves a value from the array either to a temporary location or to another location in the array itself counts as a movement. Note this means doing a swap of two values, both in the array, would require three movements:

temp=a[i]; a[i]=a[j]; a[j]=temp;.

The program reports the total time to do a sort. Time is measured in milliseconds. We recommend you do several runs of a sort on a given array and take the median value. To get more accurate runtimes, you may want to close other programs that might consume a lot of processing power or memory and therefore affect thesorting program runtimes.

For the comparison and movement counters, you might encounter overflow when sorting large arrays. You can notice this by trying increasingly larger array sizes until you see negative values for these counters.

Recursive function

Step 1: Write a recursive version of the quicksort function. Demonstrate the functions in a driver program. The function prototypes are as followings

//************************************************

// quickSort uses the QuickSort algorithm to *

// sort arr from arr[start] through arr[end]. *

//************************************************

void quickSort(int arr[], int start, int end);

//***********************************************************

// partition rearranges the entries in the array arr from *

// start to end so all values greater than or equal to the *

// pivot are on the right of the pivot and all values less *

// than are on the left of the pivot. *

//***********************************************************

int partition(int arr[], int start, int end);

//***********************************************************

// swap simply exchanges the contens of *

// values1 and value2 *

//***********************************************************

void swap (int & value1, int & value2);

Some functions maybe helpful:

int main()

{

clock_t before;

clock_t after;

double result;

int i;

int n;

int sample[MaxElements];

cout << "Enter size of set: ";

cin >> n;

if (n >= MaxElements) {

cout << "set size must be less than " << MaxElements << " ";

system("PAUSE");

exit(1);

}

generateSample(sample, n);

before = clock();

for(i=0; i<100; i++) {

run(sample, n);

}

after = clock();

result = static_cast(after - before)/CLOCKS_PER_SEC;

result = static_cast(after - before)/CLOCKS_PER_SEC;

cout << before << " " << after << " ";

cout << result << " ";

system("PAUSE");

return EXIT_SUCCESS;

}

/*

* generateSample: Generate a set of valuse of a centain size. Producres an

* array that is used to initialize the sets in our experiment.

*/

void generteSample (int sample[], int n) {

int i;

int r;

Set s;

i=0;

while (i < n) {

r = rand() %10000;

if(!s.isMember(r)) {

sample[i] = r;

i++;

}

}

}