Your job is to:
1) implement the one algorithm in these files that is not already implemented (merge sort),
2) Tell me in a comment in your code three things:
- what the runtime of this algorithm is
- whether it is "destructive"
- whether it is "in-place"
3) submit timing data along with your code to show that your code actually has the runtime you claim it does.
Your submission will be:
– A zipped copy of all the files I'm providing, with the unimplemented algorithm implemented and the comments attached to taht algorithm indicating its properties (see above).
– And, in your zip file, you should include some kind of graph showing the growth of the runtime of your implementation of the algorithm, as determined by running it under different conditions and timing it, along with the raw timing data you used to make the graph.You can make the graph however you like (hand-drawn is fine).
insertion_sort.cpp
#include <iostream> using namespace std; // insertion_sort() is built around a central loop: // That loop assumes that the elements in indices [0,largest_sorted_element_index] // are all in sorted order. The loop then looks at the element at index // largest_sorted_element_index+1 and sorts it into the sorted portion of the array. // Now, all elements in indices [0, largest_sorted_element_index+1] are sorted… // Repeat until the whole array is sorted. // // Note that the first time the loop runs, largest_sorted_element_index = 1, and so the loop // just sorts the first two elements of the array. // // Runtime: O(?) // Destructive: Y/N // In-place: Y/N void insertion_sort(int unsorted_array[], const int array_length, bool verbose = false) { int largest_sorted_element_index = -1; int placeholder_for_swapping = 0; do { // nothing to do if largest_sorted_element_index==0, but… if (largest_sorted_element_index>0) { // We can assume that unsorted_array[0] through // unsorted_array[largest_sorted_element_index] are sorted. // Knowing that, we compare unsorted_array[largest_sorted_element_index + 1] // to each of the sorted elements, starting with the largest, until // we find one that it is smaller than it. // // runtime: O(?) for (int i = largest_sorted_element_index; i >= 0; i–) { if (unsorted_array[i] <= unsorted_array[largest_sorted_element_index+1]) { placeholder_for_swapping = unsorted_array[largest_sorted_element_index+1]; // shift all elements // runtime: O(?) for (int j = largest_sorted_element_index + 1; j > i+1; j–) { unsorted_array[j] = unsorted_array[j-1]; } unsorted_array[i+1] = placeholder_for_swapping; // we've now incorporated another element into the sort break; } } } // We've now added another element to the sorted sub-array, so increment // largest_sorted_element_index. largest_sorted_element_index++; // debug output if (verbose) { cout << "after sorting: "; for (int i = 0; i < array_length; i++) { cout << unsorted_array[i] << " "; } cout << endl; } } while (largest_sorted_element_index<array_length-1); // runtime: O(?) // If we got here, then we have a sorted permutation. if (verbose) { // Print it out. cout << "sorted with insertion sort: "; for (int i = 0; i < array_length; i++) { cout << unsorted_array[i] << " "; } cout << endl; } }
insertion_sort.h
#ifndef INSERTION_SORT_H #define INSERTION_SORT_H void insertion_sort(int unsorted_array[], const int array_length, bool verbose = false); #endif
main.cpp
#include <chrono> #include <iostream> #include <random> #include "insertion_sort.h" #include "merge_sort.h" #include "permutation_sort.h" #include "selection_sort.h" using namespace std; // This is a utility function. It will be called by main() to check whether an array is sorted. // // runtime: O(?) bool _is_sorted(int sorted_array[], const int array_length) { for (int i = 0; i < array_length-1; i++) { // if element i is greater than element i+1, then this array is not in order if (sorted_array[i] > sorted_array[i+1]) { return false; } } return true; } int main() { // In order to determine the runtime of a chosen sorting algorithm, we're going to // run that sort with several different values of n (number of array // elements), and then we'll record the running time (actual time, like on // a clock) for each n. // // In an attempt to minimize the importance of random chance, we'll run // multiple iterations at each n, each iteration using a different random array. // // Then, we'll take the average of all the runtimes for each n. // // Once we do this for several values of n, we should be able to guess what // the runtime is, hopefully. // PARAMETERS you'll want to tweak bool verbose = false; const int iterations = 5; const int n_values[] = {5,10,15,20,25,30}; const int sort_function_selection = 3; // declare internal variables for random number generation default_random_engine generator; uniform_int_distribution<int> distribution(1,10); // declare internal timing variables chrono::time_point<chrono::system_clock> start, end; chrono::duration<double> elapsed_seconds; // declare internal variables used for array generation and sorting double sorting_runtimes[iterations]; double average_sorting_runtime = 0; for (const int n : n_values) { // declare array of proper length for holding unsorted values int unsorted_array[n]; cout << "N = " << n << endl; for (int i = 0; i < iterations; i++) { // create a random array of integers // print array, if verbose = true if (verbose) cout << "" << endl; if (verbose) cout << "unsorted_array: "; for (int j = 0; j < n; j++) { unsorted_array[j] = distribution(generator); if (verbose) cout << unsorted_array[j] << " "; } if (verbose) cout << endl; // start timer start = chrono::system_clock::now(); // execute chosen sorting algorithm switch(sort_function_selection) { case 1: // selection sort // runtime: O(?) selection_sort(unsorted_array, n, verbose); break; case 2: // insertion sort // runtime: O(?) insertion_sort(unsorted_array, n, verbose); break; case 3: // permutation sort // runtime: O(?) permutation_sort(unsorted_array, n, verbose); break; case 4: // merge sort // runtime: O(?) merge_sort(unsorted_array, n, verbose); break; } // stop timer and record sorting time end = chrono::system_clock::now(); elapsed_seconds = end – start; sorting_runtimes[i] = elapsed_seconds.count(); // if verbose = true, confirm that array is sorted if (verbose) { if ( _is_sorted(unsorted_array, n) ) { cout << "Array sorted." << endl; } else { cout << "Array is not sorted." << endl; } } } // Compute average of all sorting runtimes for this n. average_sorting_runtime = 0; for (int i = 0; i < iterations; i++) { average_sorting_runtime += sorting_runtimes[i]; } average_sorting_runtime /= iterations; cout << "averge sorting runtime for n=" << n << ": " << average_sorting_runtime << " seconds." << endl; cout << "" << endl; } return 0; }
merge_sort.cpp
#include <iostream> // merge_sort splits an array in halves, then splits those halves into halves, // etc., until it ends up with a single pair of elements. That pair of elements is sorted, // and then combined with the last pair of elements it was split off from (now also sorted). // This set of 4 elements is then sorted together. Then they're combined… // In this way, the array is broken down into small pieces, all the small pieces are sorted, // and the the sorted pieces are sorted together repeatedly, until the whole array has been // put back together in sorted order. // // Runtime: O(?) // Destructive: Y/N // In-place: Y/N void merge_sort(int unsorted_array[], const int array_length, bool verboe = false) { }
merge_sort.h
#ifndef MERGE_SORT_H #define MERGE_SORT_H void merge_sort(int unsorted_array[], const int array_length, bool verboe = false); #endif
permutation_sort.cpp
#include <algorithm> #include <iostream> using namespace std; // This is a utility function. It will be called by various sorting algorithms // whenever they need to check whether an array is sorted. // // runtime: O(?) bool perm_is_sorted(int sorted_array[], const int array_length) { for (int i = 0; i < array_length-1; i++) { // if element i is greater than element i+1, then this array is not in order if (sorted_array[i] > sorted_array[i+1]) { return false; } } return true; } // permutation_sort() generates permutations of the array members // one at a time and, for each permutation, checks every element // in the permutation until it finds a permutation where all // elements are in order. // // Runtime: O(?) // Destructive: Y/N // In-place: Y/N void permutation_sort(int unsorted_array[], const int array_length, bool verbose = false) { // this loop will, in the worst case loop over all permutations of unsorted_array // runtime: O(?) do { // get a permutation // runtime: O(1) next_permutation(unsorted_array, unsorted_array + array_length); // check whether this permutation is sorted // if so, break out of this loop! // runtime: O(?) if ( perm_is_sorted(unsorted_array, array_length) ) { break; } } while (true); // If we got here, then we have a sorted permutation. if (verbose) { // Print it out. cout << "sorted with permutation sort: "; for (int i = 0; i < array_length; i++) { cout << unsorted_array[i] << " "; } cout << endl; } }
permutation_sort.h
#ifndef PERMUTATION_SORT_H #define PERMUTATION_SORT_H bool perm_is_sorted(int sorted_array[], const int array_length); void permutation_sort(int unsorted_array[], const int array_length, bool verbose = false); #endif
selection_sort.cpp
#include <iostream> using namespace std; // selection_sort() is built around a central loop: // That loop starts by assuming the entire array is unsorted. It then finds the largest // element in the array (meaning largest element in indices [0, array_length-1]) and moves // that element to the last index in the array, [array_length-1]. // After that, it finds the largest remaining element in indices [0, array_length-2] and moves // that element to index [array_length-2]. // This continues until all elements have been sorted. // // Runtime: O(?) // Destructive: Y/N // In-place: Y/N void selection_sort(int unsorted_array[], const int array_length, bool verbose = false) { int largest_unsorted_element_index = -1; int placeholder_for_swapping = 0; int last_unsorted_index = array_length-1; // sort one element at a time by looping through entire unsorted portion of // the array and moving the largest element to the right do { largest_unsorted_element_index = -1; // find index of largest element in sorted_array[0,last_unsorted_index] // runtime: O(?) for (int i=0; i <= last_unsorted_index; i++) { if (largest_unsorted_element_index==-1) { largest_unsorted_element_index = i; } else { if (unsorted_array[largest_unsorted_element_index] < unsorted_array[i]) { largest_unsorted_element_index = i; } } } // swap largest element with last unsorted element of array // runtime: O(?) placeholder_for_swapping = unsorted_array[last_unsorted_index]; unsorted_array[last_unsorted_index] = unsorted_array[largest_unsorted_element_index]; unsorted_array[largest_unsorted_element_index] = placeholder_for_swapping; // decrement last_unsorted_index last_unsorted_index–; } while (last_unsorted_index>0); // runtime: O(?) }
selection_sort.h
#ifndef SELECTION_SORT_H #define SELECTION_SORT_H void selection_sort(int unsorted_array[], const int array_length, bool verbose = false); #endif