I rewrote (part of) your solution and I came up with the below code.
The TestRun() method receives an array and size and runs all the various sorting algorithms on the input and measures the time. It shows interesting results for the various inputs (already sorted, reverse sorted, multiple elements, randomly shuffled).
I'd suggest modifying my code and changing it in a way that you would measure execution in a more precise way. The problem with my implementation is that it measures the execution of a function only once. So any interference from the operating system or other running programs affect the results so comparison to other results is not really accurate.
You could achieve better results if you run it multiple times (e.g. 100) and measure the minimum, maximum and average execution time for each sorting function.
Also, in my code the sorting function contains the printing part as well. You can refactor the code for that not to be included. Or not, as if every function does the same printing, then the comparison should be not depend on this extra time.
Have fun! :)
#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <utility>
#include <vector>
#include <cstring>
void Print(const std::string & message, int a[], int size, bool addNewLine = false)
{
std::cout << message << ' ';
for (int i = 0; i < size; i++)
{
if (i > 0)
std::cout << ", ";
std::cout << a[i];
}
if (addNewLine)
std::cout << std::endl;
}
void Shuffle(int a[], int size)
{
unsigned seed = 0u; // Fixed seed, random generates the same results every time
// time based seed: unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
std::shuffle(a, a + size, std::default_random_engine(seed));
}
void Swap(int & a, int & b)
{
int temp = a;
a = b;
b = temp;
}
// NOTE: cannot pass argument as int[]. Variable sized arrays are not supported for template arguments. Hence an (int*) cast is needed.
template<typename F, typename ... Args> void RunSort(F func, Args && ... args)
{
std::chrono::high_resolution_clock::time_point startTime = std::chrono::high_resolution_clock::now();
func(std::forward<Args>(args) ...);
double duration = std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now() - startTime).count();
std::cout << " [" << duration << " ns]" << std::endl;
}
// array, left, right
int Partition(int a[], int l, int r)
{
int pivot = a[(l + r) / 2];
int i = l - 1;
int j = r + 1;
while (true)
{
while (a[++i] < pivot) /* nothing to do */;
while (a[--j] > pivot) /* nothing to do */;
if (i >= j)
return j;
Swap(a[i], a[j]);
}
}
// Insert `data` into array `a` which has a size `size`
// a: the array to be inserted into
// size: the number of elements already in the array (not the total capacity)
// data: the data to be inserted
void InsertInto(int a[], int size, int data)
{
int insertAt = size;
for (int i = 0; i < size; i++)
{
if (a[i] >= data)
{
std::memmove(&a[i + 1], &a[i], sizeof(int) * (size - i));
insertAt = i;
break;
}
}
a[insertAt] = data;
}
void InsertionSort(int originalArray[], int size)
{
int result[size];
for (int i = 0; i < size; i++)
InsertInto(result, i, originalArray[i]);
Print("Insertion-sorted array:", result, size);
}
void SelectionSort(int a[], int size)
{
for (int i = 0; i < size - 1; i++)
{
int min = i;
for (int j = i + 1; j < size; j++)
{
if (a[min] > a[j])
min = j;
}
Swap(a[i], a[min]);
}
Print("Selection-sorted array:", a, size);
}
void BubbleSort(int a[], int size)
{
int length = size;
while (length >= 1)
{
int newLength = 0; // newLength shows the last position where a swap happened. Anything beyond this is already sorted.
for (int i = 1; i < length; i++)
{
if (a[i - 1] > a[i])
{
Swap(a[i - 1], a[i]);
newLength = i;
}
}
length = newLength;
}
Print("Bubble-sorted array: ", a, size);
}
// array, left, right: array[l, r]; (left and right are inclusive)
void QuickSort(int a[], int l, int r)
{
if (l < r)
{
int p = Partition(a, l, r);
QuickSort(a, l, p);
QuickSort(a, p + 1, r);
}
}
void QuickSortWrapper(int a[], int size)
{
QuickSort(a, 0, size - 1);
Print("Quick-sorted array: ", a, size);
}
// Sources: src[l, m[; src[m, r[
// Result: dst[l, r[
void TopDownMerge(int src[], int l, int m, int r, int dst[])
{
int i = l;
int j = m;
// While there are elements in the left or right runs...
for (int k = l; k < r; k++)
{
// If left run head exists and is <= existing right run head.
if (i < m && (j >= r || src[i] <= src[j]))
{
dst[k] = src[i++];
}
else
{
dst[k] = src[j++];
}
}
}
// Sort a merge run from src to dst
// src[l, r[; (left inclusive, right exclusive)
void TopDownSplitMerge(int src[], int l, int r, int dst[])
{
if (r - l <= 1)
return;
int m = (l + r) / 2; // middle
// Split the run longer than 1 item into halves: [l, m[; [m, r[
// Sort both runs recursively from dest to src (their roles swap)
TopDownSplitMerge(dst, l, m, src); // sort the left run
TopDownSplitMerge(dst, m, r, src); // sort the right run
TopDownMerge(src, l, m, r, dst);
}
void TopDownMergeSort(int a[], int size)
{
int temp[size];
std::memcpy(temp, a, sizeof(int) * size); // Copy a to tmp
TopDownSplitMerge(temp, 0, size, a);
Print("Merge-sorted array: ", a, size);
}
void TestRun(int array[], int size)
{
Print("Array to be sorted: ", array, size, true);
int a[size];
std::memcpy(a, array, sizeof(int) * size);
RunSort(InsertionSort, (int*)a, size);
std::memcpy(a, array, sizeof(int) * size);
RunSort(SelectionSort, (int*)a, size);
std::memcpy(a, array, sizeof(int) * size);
RunSort(BubbleSort, (int*)a, size);
std::memcpy(a, array, sizeof(int) * size);
RunSort(QuickSortWrapper, (int*)a, size);
std::memcpy(a, array, sizeof(int) * size);
RunSort(TopDownMergeSort, (int*)a, size);
}
int main()
{
const int size = 10;
int array1[size] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; // already sorted
TestRun(array1, size);
std::cout << std::endl;
int array2[size] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }; // reverse sorted
TestRun(array2, size);
std::cout << std::endl;
int array3[size] = { 1, 1, 1, 2, 1, 1, 1, 2, 2, 1 }; // repeated elements
TestRun(array3, size);
std::cout << std::endl;
Shuffle(array1, size); // Shuffled array
TestRun(array1, size);
std::cout << std::endl;
}