online compiler and debugger for c/c++

code. compile. run. debug. share.
Source Code    Language
#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; }

Compiling Program...

Command line arguments:
Standard Input: Interactive Console Text
×

                

                

Program is not being debugged. Click "Debug" button to start program in debug mode.

#FunctionFile:Line
VariableValue
RegisterValue
ExpressionValue