#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;
}