online compiler and debugger for c/c++

code. compile. run. debug. share.
Source Code    Language
#include <stdio.h> #include <time.h> #include <stdlib.h> #include <string.h> #include <sys/time.h> int gCompareCalls = 0; static int compare(const void* a, const void* b) { gCompareCalls++; return strcmp(*(const char**)a, *(const char**)b); } void quickSort(char** arr, int start, int end) { int mid = (start + end) / 2; char* midValue = arr[mid]; char* tmp = NULL; int i = start, j = end; while (i <= j) { while (compare(&arr[i], &midValue) < 0) { i++; } while (compare(&arr[j], &midValue) > 0) { j--; } if (i <= j) { tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; i++; j--; } } if (start < j) { quickSort(arr, start, j); } if (i < end) { quickSort(arr, i, end); } } char** mergeSort(char** up, char** down, unsigned int left, unsigned int right) { if (left == right) { down[left] = up[left]; return down; } unsigned int middle = (left + right) / 2; char** l_buff = mergeSort(up, down, left, middle); char** r_buff = mergeSort(up, down, middle + 1, right); char** target = l_buff == up ? down : up; unsigned int l_cur = left, r_cur = middle + 1; for (unsigned int i = left; i <= right; i++) { if (l_cur <= middle && r_cur <= right) { if (compare(&l_buff[l_cur], &r_buff[r_cur]) < 0) { target[i] = l_buff[l_cur]; l_cur++; } else { target[i] = r_buff[r_cur]; r_cur++; } } else if (l_cur <= middle) { target[i] = l_buff[l_cur]; l_cur++; } else { target[i] = r_buff[r_cur]; r_cur++; } } return target; } int getTime() { struct timeval tp; gettimeofday(&tp, NULL); long int ms = tp.tv_sec * 1000 + tp.tv_usec / 1000; return ms; } int main() { const int N = 1000*1000; char** strings = new char*[N]; const char* symbols = "0123456789abcdefghijklmnopqrstuvwxyz"; srand(time(NULL)); int i, j; const int maxStringLen = 100; for (i = 0; i < N; i++) { int sLen = (rand() % maxStringLen) + 1; strings[i] = new char[sLen + 1]; strings[i][sLen] = '\0'; for (j = 0; j < sLen; j++) { strings[i][j] = symbols[rand() % 36]; } } char** systemSortedStrings = new char*[N]; for (i = 0; i < N; i++) { systemSortedStrings[i] = strings[i]; } qsort(systemSortedStrings, N, sizeof(const char*), compare); int t1, t2; // quickSort char** quickSortSortedStrings = new char*[N]; for (i = 0; i < N; i++) { quickSortSortedStrings[i] = strings[i]; } gCompareCalls = 0; t1 = getTime(); quickSort(quickSortSortedStrings, 0, N - 1); t2 = getTime(); printf("\n"); printf("quickSort\n"); for (i = 0; i < N; i++) { if (strcmp(quickSortSortedStrings[i], systemSortedStrings[i]) != 0) { printf("ERROR: incorrect sorting\n"); break; } } printf("%d ms / %d elements\n", t2 - t1, N); printf("compare() calls: %d\n", gCompareCalls); // mergeSort char** mergeSortSortedStrings = new char*[N]; char** mergeSortBuffer = new char*[N]; for (i = 0; i < N; i++) { mergeSortSortedStrings[i] = strings[i]; } gCompareCalls = 0; t1 = getTime(); mergeSortSortedStrings = mergeSort(mergeSortSortedStrings, mergeSortBuffer, 0, N - 1); t2 = getTime(); printf("\n"); printf("mergeSort\n"); for (i = 0; i < N; i++) { if (strcmp(mergeSortSortedStrings[i], systemSortedStrings[i]) != 0) { printf("ERROR: incorrect sorting\n"); break; } } printf("%d ms / %d elements\n", t2 - t1, N); printf("compare() calls: %d\n", gCompareCalls); return 0; }

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