Need help in C++ Level 3-4

i pass the level 1 and 2 the Level 3-4 need to slow tabular data and plots

Task

Write a program that implements several sorting algorithms and use it to demonstrate the comparative performance of the algorithms for a variety of datasets. Background he skeleton program sorting.cpp contains a main function for testing the operation of several sort algorithms over various data sizes and dataset organisations. The program understands the following arguments: -i insertion sort -s selection sort (default) -q quicksort -a (already) sorted dataset -v reverse-sorted dataset -r random dataset (default) -n no sorting x generate a dataset of size x (default 10000)

Level 1: Basic sorts Implement the selectionSort and insertionSort functions. Note that you can base your code on the sample code used in lectures, although you will need to modify it from passing the data using an array and two indexes to passing it using two pointers. The program will check that the final list is sorted correctly.

Level 2: Quicksort Implement the quickSort function. The real work of quicksort happens in the partition operation, so it is probably best to define a separate function to do the partitioning.

Level 3: Profiling Gather data on the number of times that each algorithm compares and swaps items. A simple strategy is to use variables to count the comparisons and swaps. The skeleton code declares comparisons and swaps variables for just this purpose. To make use of them, modify your code to increment each variable where appropriate and then uncomment the output statements to display their final values. When you have profiling working, run the program and record the number of compares and swaps for each combination of algorithm (-i, -s, and -q) and dataset organisation (-a, -v, and -r). Use dataset sizes of 1000, 2000, 5000, 10,000, 50000, and 100000. In the worst case, execution should not take much longer than 30 seconds. For each run, compute a normalised execution count by dividing the actual count by the dataset size. For example, if quicksort with a random dataset containing 10000 elements performed 161619 comparisons, the normalised count would be 161619/10000 or about 16.2. Finally, plot the comparison results (for the options -ia, -iv, -ir, -sa, -sv, -sr, -qa, -qv, and -qr) as separate lines on a single set of axes with dataset size on the horizontal axis and execution count on the vertical axis. Repeat for swaps. Choose scales so that the full range of values can be displayed and label the lines so you know which one is which. You may find that using a log-log plot shows the values over the full range better.

Level 4: Improving quicksort A simple implementation of quicksort is likely to perform badly for certain datasets. For example, the implementation used as an example in lectures performs very poorly if the dataset is in reverse-sorted order. The poor performance can be avoided by choosing a better pivot for the partitioning step. Common strategies include selecting a random element or using the median of the first, middle, and last elements. In any case, the chosen pivot is swapped with the last element before proceeding to do the partition as before. Read about and implement one of the improvements to quicksort and show (by adding its profile data to the graphs of Level 3) how much improvement you have achieved. Include a brief description of the method you implemented to improve quicksorts performance.

the Code in level 1-2 :

#include  #include  #include  #include  using namespace std; static long comparisons = 0; static long swaps = 0; void swap(int* a, int* b) { swaps++;//increment the swap int temp=*a;//get the element in temp *a=*b;//write the value of b in a *b=temp;//write the value of temp in b // add code here } void selectionSort(int* first, int* last) { // add code here int n=last-first; //get the size by subtracting last and first pointet for(int i=0;i=0&&first[j]>value) //iterate until value is less than jth index { comparisons++;//increment the comparisons swaps++; first[j+1]=first[j];//shift the element forward j--;//decrement j } first[j+1]=value;//assign the value at j+1 index } // add code here } //partition array that takes arrays first address as input and no. of elements to consider int partition(int *first,int n) { //assuming pivot to be the last element int pivot=*(first+n-1);//assign value of pivot int i=-1; //start before 0 int low=0;//assign low as 0 to start the iteration int high=n-1;//the value upto which iteration goes for(int j=low;j0)//if there is any numbers in array { int p=partition(first,n);//get the pivot //pivot comes to its original location quickSort(first,first+p);//quicksort for left half quickSort(first+p+1,last);//quicksort for right half } // add code here } int main(int argc, char** argv) { string algorithm = "insertion"; string dataset = "random"; for (int c; (c = getopt(argc, argv, "ravqsin")) != -1;) { switch (c) { case 'r': dataset = "random"; break; case 'a': dataset = "sorted"; break; case 'v': dataset = "reverse"; break; case 'q': algorithm = "quicksort"; break; case 's': algorithm = "selection"; break; case 'i': algorithm = "insertion"; break; case 'n': algorithm = "none"; break; } } argc -= optind; argv += optind; const int size = argc > 0 ? atoi(argv[0]) : 10000; int* data = new int[size]; if (dataset == "sorted") { for (int i = 0; i < size; ++i) { data[i] = i; } } else if (dataset == "reverse") { for (int i = 0; i < size; ++i) { data[i] = size - i - 1; } } else if (dataset == "random") { for (int i = 0; i < size; ++i) { data[i] = rand() % size; } } if (algorithm == "quicksort") { quickSort(data, data + size); } else if (algorithm == "selection") { selectionSort(data, data + size); } else if (algorithm == "insertion") { insertionSort(data, data + size); } for (int i = 1; i < size; i++) { if (data[i] < data[i - 1]) { cout << "Oops!" << ' '; exit(1); } } cout << "OK" << ' '; cout << "Algorithm: " << algorithm << ' '; cout << "Data set: " << dataset << ' '; cout << "Size: " << size << ' '; // Uncomment for level 3 and 4 //cout << "Comparisons: " << comparisons << ' '; //cout << "Swaps: " << swaps << ' '; delete[] data; return 0; }

thnaks