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