Question

Can I get some help with this question for c++ if you can add some comments too to help understand that will be much appreciated.

Background The skeleton program sorting.cpp contains a main function for testing the operation of several sort algorithms over various data sizes and data set organisations. The program understands the following options: -i insertion sort selection sort (the default) quicksort (already) sorted data set -S -q -a reverse-sorted data set -V random data set (the default) generate a data set of size n (default 10,000) -r Level 1: Basic sorts Implement the selectionSo rt 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

Code:

#include <cstdlib>

#include <getopt.h>

#include <iostream>

#include <string>

using namespace std;

static long comparisons = 0;

static long swaps = 0;

void swap(int *a, int *b)

{

    // add code here

}

void selectionSort(int *first, int *last)

{

    // add code here

}

void insertionSort(int *first, int *last)

{

    // add code here

}

void quickSort(int *first, int *last)

{

    // add code here

}

int main(int argc, char **argv)

{

    string algorithm = "selection";

    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!" << '\n';

            exit(1);

        }

    }

    cout << "OK" << '\n';

    cout << "Algorithm:   " << algorithm << '\n';

    cout << "Data set:    " << dataset << '\n';

    cout << "Size:        " << size << '\n';

    return 0;

}

Answer 1

#include <cstdlib>

#include <getopt.h>

#include <iostream>

#include <string>

using namespace std;

static long comparisons = 0;

static long swaps = 0;

void swap(int *a, int *b)

{

    // add code here
   int t = *a;
   *a = *b;
   *b = t;

}

void selectionSort(int *first, int *last)

{

    // add code here
   int min_element;
   int size = *(&first+1)-first;   // calculating the size of array
  
   for(int i=0;i<size-1;i++)
   {
       min_element = i;           // it will store the index of minimum element
      
       for(int j=i+1;j<size;j++)
       {
           if(*(first+j) < *(first+min_element))
           {
               min_element = j;
           }
       }
      
       swap(first+min_element,first+i);// call swap at the end of inner loop to exchange value of minimum to its right place
   }

}

void insertionSort(int *first, int *last)

{

    // add code here
   int size = *(&first+1)-first;   //calculating size of array

    for (int i = 1; i < size; i++)
    {
        
        int j = i - 1;               
  
       int pivot = *(first+i);   // it will store the element which is to be placed in array at its right position

       for(;j>=0 && *(first+j)>pivot;j--)
       {
           *(first+j+1) = *(first+j);   // shifting elements one position till we find the right place for pivot
       }
       *(first+j+1) = pivot;
    }

}

// function to find the divide point of array
int divide(int *first, int start, int end)
{
   int x = *(first+end); // we will always choose last element of array as the divide point
  
   int i = start-1;
  
   for(int j=start ;j<end-1;j++)
   {
       if(*(first+j) < x)
       {
           i++;
           swap(first+i,first+j);
       }
   }
   swap(first+i+1,first+end);   // swap the last element which was the divide point in our case with the actual position
   return i+1;       // return i+1 which is the current divide point on left side elements are smaller and on right bigger
}
void quicksort_divide(int *first,int start,int end)
{
   if(start < end)
   {
       int pivot = divide(first,start,end);   // call to partition which will return the poisition for pivot to divide array
      
       quicksort_divide(first,start,pivot-1); // recursive call to left array for division
       quicksort_divide(first,pivot+1,end);   // recursive call to right array for division
      
   }
}

void quickSort(int *first, int *last)

{

    // add code here
   int size = *(&first+1)-first;   // calculating size of array
  
   quicksort_divide(first,0,size-1);

}

int main(int argc, char **argv)

{

    string algorithm = "selection";

    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!" << '\n';

            exit(1);

        }

    }

    cout << "OK" << '\n';

    cout << "Algorithm:   " << algorithm << '\n';

    cout << "Data set:    " << dataset << '\n';

    cout << "Size:        " << size << '\n';

    return 0;

}