Using the code below is someone able to implement question 3 and 4. Thanks heaps
Prac 5 is the code below as referenced in the task!
#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; }
//Implementing the Code in selection sort, insertion sort and quickSort
int* variable(int* start, int* stop) { //where code is added for the variable int* number_1 = start; int* pivot = stop; // level 4, changing the pivot for (int* number_2 = start + 1; number_2
void quickSort(int* start, int* stop) { //where code is added for quicksort if (*start
void insertionSort(int* start, int* stop) { //where code is added for insertion sort for (int* number_1 = start + 1; number_1 start; -- number_2) { if (*number_2
void selectionSort(int* start, int* stop) { //where code is added for selection sort for (int* number_1 = start; number_1
int* i = start; int* j = mid; int* k = temp;
while (i
for (i = start, k = temp; i != stop; ++i, ++k) { counted_swap(*i, *k); } }
void mergeSort(int* start, int* stop) { if (stop - start
int main(int argc, char** argv) {
string algorithm = "quicksort"; string dataset = "reversed"; 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
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); }
cout
// uncomment for checkpoints 3 and 4 cout
}
Task Practical sort implementations usually combine more than one sorting algorithm, attempting to take advantage of the best characteristics of each. For example, a straightforward but effective approach for general-purpose sorting is to use quicksort, but with a switch-over to insertion sort when the size of the lists that result from the partitioning falls below a threshold value. The structure of the combined sort would be like this sort (.. .)- if size is less than threshold do an insertion sort a quicksort partition recursively sort the first part recursively sort the second part This approach is generally faster that using pure quicksort because insertion sort has a lower overhead than quicksort and is thus faster, provided the length of the list is small enough. To get the greatest speedup, the threshold for switching to insertion sort needs to be carefully chosen: too large, and the greater algorithmic cost of the insertion sort will overwhelm any lower overheads; too small, and the potential benefits of the combined approach are wasted 3. Design an experiment to determine the best "cutover" threshold size for the combined "quicksort-plus-insertion-sort" implementation. You'll need to consider a range of data sizes, including both random and "worst-case" data sets Write a program that could be used to perform the experiment. You'll need to provide the sort code itself (use your code from prac 5) as well as a suitable main function for testing it (adapt the main function from prac 5) Your experimental design should be sufficiently detailed that you could hand the task over to a tester who is not familiar with sorting algorithms or even with programming. Ideally, the tester should only need to run the program under specified conditions and record the results Run your experiment and report on the findings. Your report should include the data you gather, an analysis of that data, and a clear recommendation as to the best cutover threshold Consider how best to present your results. You'll certainly want to tabulate the data, but you might also find it helpful to plot it as well. Because the actual timeswill be heavily dependent on the data size, you might find it useful to normalise the times against the "ideal" time (by dividing by n log n) before plotting them 4. Task Practical sort implementations usually combine more than one sorting algorithm, attempting to take advantage of the best characteristics of each. For example, a straightforward but effective approach for general-purpose sorting is to use quicksort, but with a switch-over to insertion sort when the size of the lists that result from the partitioning falls below a threshold value. The structure of the combined sort would be like this sort (.. .)- if size is less than threshold do an insertion sort a quicksort partition recursively sort the first part recursively sort the second part This approach is generally faster that using pure quicksort because insertion sort has a lower overhead than quicksort and is thus faster, provided the length of the list is small enough. To get the greatest speedup, the threshold for switching to insertion sort needs to be carefully chosen: too large, and the greater algorithmic cost of the insertion sort will overwhelm any lower overheads; too small, and the potential benefits of the combined approach are wasted 3. Design an experiment to determine the best "cutover" threshold size for the combined "quicksort-plus-insertion-sort" implementation. You'll need to consider a range of data sizes, including both random and "worst-case" data sets Write a program that could be used to perform the experiment. You'll need to provide the sort code itself (use your code from prac 5) as well as a suitable main function for testing it (adapt the main function from prac 5) Your experimental design should be sufficiently detailed that you could hand the task over to a tester who is not familiar with sorting algorithms or even with programming. Ideally, the tester should only need to run the program under specified conditions and record the results Run your experiment and report on the findings. Your report should include the data you gather, an analysis of that data, and a clear recommendation as to the best cutover threshold Consider how best to present your results. You'll certainly want to tabulate the data, but you might also find it helpful to plot it as well. Because the actual timeswill be heavily dependent on the data size, you might find it useful to normalise the times against the "ideal" time (by dividing by n log n) before plotting them 4
