- In This Lab You Will Write A C Program That Implements And Tests Three Sorting Algorithms You Must Implement These Yo 1 (263.67 KiB) Viewed 11 times
#include <iostream>
#include <chrono>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
using namespace std::chrono; // Namespace for fancy mstiming
bool verify_sorted(int arr[], int n)
{
for (int i = 0; i < n - 1; i++)
if (arr > arr[i + 1])
return false;
return true;
}
int main()
{
int n2avg = 10;
char name[] = "<Your name(s) here>";
printf("\nCCPS616 - Lab 1 – %s\n", name);
printf("Each result is the average of %dtrials\n\n", n2avg);
/****************************************/
/************ SELECTION SORT ************/
/****************************************/
{
// Feel free to tinker with thesesizes.
// Simply add new value(s) to thearray sel_test_sizes[]
int sel_test_sizes[] = { 2000, 4000,8000, 16000 };
// for every array size insel_test_sizes...
for (int n : sel_test_sizes)
{
// Create arrays ofsize n for each trial
int *nums = newint[n];
int *sel_nums = newint[n];
// Seed RNG, fill numswith random values between 1 and 4n
srand(time(NULL));
for (int i = 0; i <n; i++)
nums= rand() % (n * 4) + 1;
printf("SELECTION %5d nums: ", n);
int time_sum = 0;
// Sadly, replit isvery noisy. Average over n2avg trials
for (int k = 0; k <n2avg; k++)
{
// copyunsorted array into sel_nums
//ensures we start with the same unsorted array for each trial
std::copy(nums, nums + n, sel_nums);
// FancyC++11 code for timing in milliseconds
autobegin = high_resolution_clock::now();
/********** CALL SELECTION SORT HERE **********/
//Implement this function however you want with one constraint:
// Theinput (sel_nums) must be sorted. Don't return a new array.
//selection_sort( ... );
//*********************************************/
// Morefancy C++11 code for timing in milliseconds
auto dur= high_resolution_clock::now() - begin;
time_sum+= (int)duration_cast<milliseconds>(dur).count();
//Verify list is sorted, see verify_sort() above
assert(verify_sorted(sel_nums, n));
std::cout << "." << std::flush;
}
printf(" Avg: %dms\n",time_sum / n2avg);
delete[] nums;
delete[] sel_nums;
}
}
/****************************************/
/********** END SELECTION SORT **********/
/****************************************/
/****************************************/
/******* MERGE & MERGE-SEL SORT *********/
/****************************************/
{
// Feel free to tinker with thesesizes.
// Simply add new value(s) to thearray merge_test_sizes[]
int merge_test_sizes[] = { 128000,256000, 512000, 1024000 };
for (int n : merge_test_sizes)
{
// Create arrays ofsize n for each trial
int *nums = newint[n];
int *merge_nums = newint[n];
int *merge_sel_nums =new int[n];
// Seed RNG, fill numswith random values between 1 and 4n
srand(time(NULL));
for (int i = 0; i <n; i++)
nums= rand() % (n * 4) + 1;
printf("MERGE %7d nums: ", n);
int time_sum = 0;
for (int k = 0; k <n2avg; k++)
{
std::copy(nums, nums + n, merge_nums);
autobegin = high_resolution_clock::now();
/********** CALL MERGE SORT HERE **********/
//Implement this function however you want with one constraint:
// Theinput (merge_nums) must be sorted. Don't return a new array.
//merge_sort( ... );
//*****************************************/
auto dur= high_resolution_clock::now() - begin;
time_sum+= (int)duration_cast<milliseconds>(dur).count();
assert(verify_sorted(merge_nums, n));
std::cout << "." << std::flush;
}
printf(" Avg: %dms\n",time_sum / n2avg);
printf("MERGE-SEL %7d nums: ", n);
time_sum = 0;
for (int k = 0; k <n2avg; k++)
{
std::copy(nums, nums + n, merge_sel_nums);
autobegin = high_resolution_clock::now();
/********** CALL MERGE-SEL SORT HERE **********/
//Implement this function however you want with one constraint:
// Theinput (merge_sel_nums) must be sorted. Don't return a newarray.
//merge_sel_sort( ... );
//**********************************************/
auto dur= high_resolution_clock::now() - begin;
time_sum+= (int)duration_cast<milliseconds>(dur).count();
assert(verify_sorted(merge_sel_nums, n));
std::cout << "." << std::flush;
}
printf(" Avg: %dms\n",time_sum / n2avg);
delete[] nums;
delete[] merge_nums;
delete[] merge_sel_nums;
}
}
/****************************************/
/****** END MERGE & MERGE-SEL SORT ******/
/****************************************/
printf("\nThe values of ax tested were: <You tellme>\n");
printf("The values of ax that yielded the best resultswas <You tell me>\n");
}
In this lab you will write a C++ program that implements and tests three sorting algorithms. You must implement these yourself without linking any external libraries. Your lab should be completed in a single cpp file called lab1.cpp, and should compile at the command line in replit very simply as follows: g++ -o lab1 lab1.cpp Please do not submit labs that don't compile. I will not debug syntax errors when marking. Lab Description We've done a lot of hand-waving about O(n²) sorting algorithms being faster than O(nlogn) sorting algorithms when the problem gets below a certain size. In this lab, we will put such claims to the test. You will implement three sorting algorithms: First, implement standard, out-of-the-box Selection sort and Merge sort. Each should be in their own function(s). An unsorted array goes in and gets sorted. Sorting should be done on the original array (do not return a new one). Implementation details beyond that are up to you. Next, implement a modified Merge sort (henceforth referred to as "MergeSel") that cuts to Selection sort when the sub-arrays get small enough. I.e., instead of recursively calling Merge sort all the way down to a subarray of a single element, call Selection sort instead when the subarrays are g++ -o labl labl_sol.cpp && ./labl CCPS616 - Lab 1 - Alex Ufkes Each result is the average of 10 trials 2000 nums: 4000 nums: 8000 nums: 16000 nums: 128000 nums: 128000 nums: 256000 nums: 256000 nums: 512000 nums: 512000 nums: 1024000 nums: MERGE-SEL 1024000 nums: SELECTION SELECTION SELECTION SELECTION MERGE MERGE-SEL MERGE MERGE-SEL MERGE MERGE-SEL MERGE Avg: 11ms Avg: 38ms Avg: 167ms Avg: 909ms Avg: 102ms Avg: 103ms Avg: 185ms Avg: 150ms Avg: 624ms Avg: 421ms Avg: 911ms Avg: 759ms The values of ax tested were: The values of ax that yielded the best results was >
Notes replit seems to be very, very inconsistent when it comes to runtimes. Subsequent runtimes of the same sorting algorithm often vary by over 100%. I've tried to account for this in the tester by averaging over many trials, but you will likely still observe inconsistent results. Don't be afraid to rerun your code several times, or test locally on your own PC. When I test my code on my own PC, things are much more consistent (and Mergesel dominates Merge sort): C:\Users\aufke\Google Drive\ Teaching\CCPS 6... CCPS616- Lab 1 - Alex Ufkes Each result is the average of 10 trials SELECTION SELECTION 2000 nums: 4000 nums: SELECTION 16000 SELECTION MERGE 128000 nums: MERGE-SEL 128000 nums: MERGE 256000 nums: MERGE-SEL 256000 nums: MERGE 512000 nums: MERGE-SEL 512000 nums: MERGE 1024000 nums: MERGE-SEL 1024000 nums: Press any key to continue. - 8000 nums: nums: Avg: 2ms Avg: 9ms Avg: 35ms Avg: 139ms Avg: 33ms Avg: 17ms Avg: 68ms Avg: 36ms Avg: 139ms Avg: 75ms Avg: 287ms Avg: 156ms X In addition, be sure to properly manage your memory. Memory leaks and inefficient use of very large arrays in C/C++ can also lead to runtime inconsistencies (or crashes).