sorting problems
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