1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234

/**Purpose of code: Create "list" class that represents a list of numbers of a given size
Create a function that is able to randomize your list of numbers
Implement the following methods to sort your List class:
 insertion sort (works with 8 values)
 merge sort (works with 6 values)
 quick sort (works with 6 values)
 median sort
Run each of these methods and record the run time of each at List lengths of:
 100
 200
 300
 400
 500
 600
 700
 800
 900
 1000
Each of these 10 times and record the average of each run time
 write these out to a csv file
In excel (or similar tool) graph the average run time for each sorting method on the same plot to compare how each performs on each List size.
Repeat steps 34 when you attempt to sort an alreadysorted list of numbers and record the findings
Repeat steps 34 when you attempt to sort a reversesorted list of numbers and record the findings
**/
#include <iostream>
#include <stdio.h>
#include <list>
#include <chrono>
#include <algorithm>
using namespace std::chrono;
using namespace std;
// Part 2 to using Merge sort to sort my list
void merge(int arr[], int z, int l, int arr_size)
{
int n1 = l  z + 1;
int n2 = arr_size  l;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[z + i];
for (int j = 0; j < n2; j++)
R[j] = arr[l + 1 + j];
int i = 0;
int j = 0;
int k = z;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
//Function that uses Merge sort to sort my list
void mergeSort(int arr[], int z, int arr_size)
{
int l;
if(z < arr_size)
{
l = (z + arr_size)/ 2;
mergeSort(arr, z, l);
mergeSort(arr, z+1, arr_size);
merge(arr, z, l, arr_size); //< not declared in scope?
}
}
//Function to print out results of sorting using Merge sort method
void mergePrint(int arr[], int arr_size)
{
int i;
cout << "Using Merge Sort method: ";
for (i = 0; i < arr_size; i++)
cout << arr[i] << " ";
}
//Part 3 to using Quick sort to sort my list
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
//Part 2 to using Quick sort to sort my list
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low  1); // Index of smaller element and indicates the right position of pivot found so far
for (int j = low; j <= high  1; j++)
{
// If current element is smaller than the pivot
if (arr[j] < pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
//Function that uses Quick sort to sort my list
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi  1);
quickSort(arr, pi + 1, high);
}
}
//Function to print out results of sorting using Quick sort method
void quickPrint(int arr[], int arr_size)
{
int i;
cout << "Using Quick Sort method: ";
for (i = 0; i < arr_size; i++)
cout << arr[i] << " ";
}
/*
//Function that uses Median sort to sort my list
void medianSort()
{
}
//Function to print out results of sorting using Median sort method
void medianPrint()
{
int i;
cout << "Using Median Sort method: ";
for (i = 0; i < arr_size; i++)
cout << arr[i] << " ";
}
*/
//Function that uses Insertion sort to sort my list
void insertionSort(int arr[], int arr_size)
{
int i,j,k;
for (i = 1; i < arr_size; i++)
{
k = arr[i];
j = i  1;
while (j >= 0 && arr[j] > k)
{
arr[j + 1] = arr[j];
j = j  1;
}
arr[j + 1] = k;
}
}
//Function to print out results of sorting using Insertion sort method
void insertionPrint(int arr[], int arr_size)
{
int i;
cout << "Using Insertion Sort method: ";
for (i = 0; i < arr_size; i++)
cout << arr[i] << " ";
}
int main()
{
// Declaring numbers
int arr[] = {6, 10, 12, 3, 7, 1}; // tried with 8 values but Merge sort does not sort entirely
int arr_size = sizeof(arr)/ sizeof(arr[0]);
//Captures time it takes to run Merge Sort function
auto mStart = high_resolution_clock::now();
//Call Merge sort functions
mergeSort(arr, 0, arr_size  1);
mergePrint(arr, arr_size);
auto mStop = high_resolution_clock::now();
auto mDuration = duration_cast<microseconds>(mStop  mStart);
cout << "\nTime taken by Merge Sort function : "<< mDuration.count() << " microseconds" <<endl;
//Captures time it takes to run Quick Sort function
auto qStart = high_resolution_clock::now();
//Call Quick sort functions
quickSort(arr, 0, arr_size  1);
quickPrint(arr, arr_size);
auto qStop = high_resolution_clock::now();
auto qDuration = duration_cast<microseconds>(qStop  qStart);
cout << "\nTime taken by Quick Sort function : "<< qDuration.count() << " microseconds" <<endl;
//Captures time it takes to run Insertion Sort function
auto iStart = high_resolution_clock::now();
//Calls Insertion Sort functions
insertionSort(arr, arr_size);
insertionPrint(arr, arr_size);
auto iStop = high_resolution_clock::now();
auto iDuration = duration_cast<microseconds>(iStop  iStart);
cout << "\nTime taken by Insertion Sort function : "<< iDuration.count() << " microseconds";
return 0;
}
 