code in c++ AND YOU MUST ADD THE SORT FUNCTIONS INTO THE THE SKELTON CODE SHOW BELOW. IT TELLS YOU WHERE TO ADD THE CODE
code in c++ AND YOU MUST ADD THE SORT FUNCTIONS INTO THE THE SKELTON CODE SHOW BELOW. IT TELLS YOU WHERE TO ADD THE CODE :)
#include
#include
#include
using namespace std;
long compares; // for counting compares
long swaps; // for counting swaps
bool counted_less(int n1, int n2) {
++compares;
return n1
}
void counted_swap(int& n1, int& n2) {
++swaps;
int t = n1;
n1 = n2;
n2 = t;
}
void selectionSort(int* start, int* stop) {
// add code here
}
void insertionSort(int* start, int* stop) {
// add code here
}
void quickSort(int* start, int* stop) {
// add code here
}
void merge(int* start, int* mid, int* stop) {
int temp[stop - start];
int* i = start;
int* j = mid;
int* k = temp;
while (i
if (i == mid) {
counted_swap(*k++, *j++);
} else if (j == stop) {
counted_swap(*k++, *i++);
} else if (counted_less(*j, *i)) {
counted_swap(*k++, *j++);
} else {
counted_swap(*k++, *i++); // bias to left for stability
}
}
for (i = start, k = temp; i != stop; ++i, ++k) {
counted_swap(*i, *k);
}
}
void mergeSort(int* start, int* stop) {
if (stop - start
int* mid = start + (stop-start)/2;
mergeSort(start, mid);
mergeSort(mid, stop);
merge(start, mid, stop);
}
int main(int argc, char** argv) {
string algorithm = "selection sort";
string dataset = "random";
int size = 1000;
for (int c; (c = getopt(argc, argv, "ravmqsi")) != -1;) {
switch(c) {
case 'r': dataset = "random"; break;
case 'a': dataset = "already sorted"; break;
case 'v': dataset = "reversed"; break;
case 'm': algorithm = "merge sort"; break;
case 'q': algorithm = "quicksort"; break;
case 's': algorithm = "selection sort"; break;
case 'i': algorithm = "insertion sort"; break;
}
}
argc -= optind;
argv += optind;
if (argc > 0) size = atoi(argv[0]);
int* data = new int[size];
if (dataset == "already sorted") {
for (int i = 0; i
} else if (dataset == "reversed") {
for (int i = 0; i
} else if (dataset == "random") {
for (int i = 0; i
}
compares = 0;
swaps = 0;
if (algorithm == "merge sort") {
mergeSort(data, data+size);
} else if (algorithm == "quicksort") {
quickSort(data, data+size);
} else if (algorithm == "selection sort") {
selectionSort(data, data+size);
} else if (algorithm == "insertion sort") {
insertionSort(data, data+size);
}
for (int i = 1; i
if (data[i]
cout
exit(1);
}
}
cout
cout
cout
}
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: insertion sort -s selection sort (the default) qquicksort -m merge sort -a already-sorted data set -vreverse-sorted data set rrandom data set (the default) n generate a data set of size n (default 10000) Level 1: Basic Sorts Implement the selectionsort and insertionSort functions. Note that you can base your code on the the sample code used in lectures, although you'll need to change it from passing the data using an array and 2 indexes, to passing it using two pointers. Level 2: Quicksort Implement the quickSort function. The real work of quicksort happens in the partition operation, so it's probably best to define a separate function to do the partitioning. 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: insertion sort -s selection sort (the default) qquicksort -m merge sort -a already-sorted data set -vreverse-sorted data set rrandom data set (the default) n generate a data set of size n (default 10000) Level 1: Basic Sorts Implement the selectionsort and insertionSort functions. Note that you can base your code on the the sample code used in lectures, although you'll need to change it from passing the data using an array and 2 indexes, to passing it using two pointers. Level 2: Quicksort Implement the quickSort function. The real work of quicksort happens in the partition operation, so it's probably best to define a separate function to do the partitioning
Step by Step Solution
There are 3 Steps involved in it
Step: 1
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
Authors: Jeng-Shyang Pan ,Shyi-Ming Chen ,Ngoc-Thanh Nguyen
2012th Edition
3642284892, 978-3642284892
