#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
struct DataWrapper
{
char* pRawData;
int len;
DataWrapper(char* pRawData, int len)
{
this->pRawData = pRawData;
this->len = len;
}
};
struct Element
{
DataWrapper* data;
Element* next;
Element()
{
this->data = NULL;
this->next = NULL;
}
};
struct LinkedList
{
Element* head;
Element* tail;
int len;
LinkedList()
{
this->head = NULL;
this->tail = NULL;
this->len = 0;
}
void addToHead(Element* element)
{
if (this->len == 0) {
element->next = NULL;
this->head = element;
this->tail = element;
this->len++;
return;
}
element->next = this->head;
this->head = element;
this->len++;
}
void addToTail(Element* element)
{
element->next = NULL;
if (this->len == 0) {
this->head = element;
this->tail = element;
this->len++;
return;
}
this->tail->next = element;
this->tail = element;
this->len++;
}
};
int COMPARE_ELEMENTS_COUNT = 0;
int CompareElements(Element* e1, Element* e2)
{
COMPARE_ELEMENTS_COUNT++;
int res = memcmp(e1->data->pRawData, e2->data->pRawData, (e1->data->len < e2->data->len ? e1->data->len : e2->data->len));
if (res == 0) {
return (e1->data->len - e2->data->len);
}
return res;
}
void performMerge(LinkedList** buffer, int toIndex, int fromIndex)
{
Element* e1 = buffer[toIndex]->head;
Element* e2 = buffer[fromIndex]->head;
Element* tmp = NULL;
int firstAdd = 1;
while (e1 != NULL && e2 != NULL) {
if (CompareElements(e1, e2) <= 0) {
tmp = e1;
e1 = e1->next;
} else {
tmp = e2;
e2 = e2->next;
}
if (firstAdd) {
buffer[toIndex]->head = tmp;
buffer[toIndex]->tail = tmp;
buffer[toIndex]->len = 1;
firstAdd = 0;
} else {
buffer[toIndex]->tail->next = tmp;
buffer[toIndex]->tail = tmp;
buffer[toIndex]->len++;
}
}
while (e1 != NULL) {
tmp = e1->next;
buffer[toIndex]->addToTail(e1);
e1 = tmp;
}
while (e2 != NULL) {
tmp = e2->next;
buffer[toIndex]->addToTail(e2);
e2 = tmp;
}
buffer[toIndex]->tail->next = NULL;
}
static int compareBySizeAsc(const void* a, const void* b)
{
return ((*(LinkedList**)a)->len - (*(LinkedList**)b)->len);
}
void mergeLists(LinkedList** buffer, int &bufferLength)
{
int count = bufferLength * 3 / 4;
qsort(buffer, bufferLength, sizeof(LinkedList*), compareBySizeAsc);
int i, j;
int count2 = count / 2;
while (count2 >= 3) {
for (int n = 0; n < count2; n++) {
performMerge(buffer, n, n + count2);
}
count2 /= 2;
}
performMerge(buffer, 0, 1);
performMerge(buffer, 2, count);
performMerge(buffer, 0, 2);
i = count + 1;
for (j = i; j < bufferLength; j++) {
buffer[j - i + 1] = buffer[j];
}
bufferLength = bufferLength - i + 1;
}
LinkedList* voronkaSort(LinkedList* &list)
{
const int maxBufferSize = 1024;
LinkedList** buffer = new LinkedList*[maxBufferSize];
int bufferLength = 0;
LinkedList* voronka = new LinkedList();
Element* next = NULL;
for (Element* cur = list->head; cur != NULL; cur = next) {
next = cur->next;
if (voronka->len == 0) {
voronka->addToTail(cur);
continue;
} else {
if (CompareElements(cur, voronka->tail) >= 0) {
voronka->addToTail(cur);
continue;
} else if (CompareElements(cur, voronka->head) <= 0) {
voronka->addToHead(cur);
continue;
}
}
if (bufferLength == maxBufferSize) {
mergeLists(buffer, bufferLength);
}
buffer[bufferLength] = voronka;
bufferLength++;
voronka = new LinkedList();
voronka->addToTail(cur);
}
if (bufferLength == maxBufferSize) {
mergeLists(buffer, bufferLength);
}
if (voronka->len > 0) {
buffer[bufferLength] = voronka;
bufferLength++;
}
qsort(buffer, bufferLength, sizeof(LinkedList*), compareBySizeAsc);
int count2 = bufferLength / 2;
while (count2 >= 1) {
for (int n = 0; n < count2; n++) {
performMerge(buffer, n, n + count2);
}
if (bufferLength % 2 == 1 && bufferLength >= 2) {
performMerge(buffer, count2 - 1, bufferLength - 1);
}
bufferLength = count2;
count2 /= 2;
}
list = buffer[0];
delete []buffer;
}
void quickSort(char** arr, int start, int end)
{
int mid = (start + end) / 2;
char* midValue = arr[mid];
char* tmp = NULL;
DataWrapper data(midValue, strlen(midValue));
Element midValueElement;
midValueElement.data = &data;
midValueElement.next = NULL;
Element arrElement;
DataWrapper arrData(NULL, 0);
arrElement.data = &arrData;
arrElement.next = NULL;
int i = start, j = end;
while (i <= j) {
arrData.pRawData = arr[i];
arrData.len = strlen(arr[i]);
while (CompareElements(&arrElement, &midValueElement) < 0) {
i++;
arrData.pRawData = arr[i];
arrData.len = strlen(arr[i]);
}
arrData.pRawData = arr[j];
arrData.len = strlen(arr[j]);
while (CompareElements(&arrElement, &midValueElement) > 0) {
j--;
arrData.pRawData = arr[j];
arrData.len = strlen(arr[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);
}
}
static int compareStrings(const void* a, const void* b)
{
return strcmp(*(const char**)a, *(const char**)b);
}
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 = 10000;
char** strings = new char*[N];
const char* symbols = "0123456789abcdefghijklmnopqrstuvwxyz";
srand(time(NULL));
int i, j;
const int maxStringLen = 20;
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*), compareStrings);
int t1, t2;
// voronkaSort
LinkedList* list = new LinkedList();
for (i = 0; i < N; i++) {
DataWrapper* data = new DataWrapper(strings[i], strlen(strings[i]));
Element* element = new Element();
element->data = data;
list->addToTail(element);
}
COMPARE_ELEMENTS_COUNT = 0;
t1 = getTime();
voronkaSort(list);
t2 = getTime();
char** voronkaSortedStrings = new char*[N];
int n = 0;
for (Element* cur = list->head; cur != NULL; cur = cur->next) {
voronkaSortedStrings[n] = cur->data->pRawData;
n++;
}
printf("voronkaSort\n");
for (i = 0; i < N; i++) {
if (strcmp(voronkaSortedStrings[i], systemSortedStrings[i]) != 0) {
printf("ERROR: incorrect sorting\n");
break;
}
}
if (i == N) {
printf("correct sorting\n");
}
printf("%d ms / %d elements\n", t2 - t1, N);
printf("CompareElements() calls: %d\n", COMPARE_ELEMENTS_COUNT);
// quickSort
char** quickSortSortedStrings = new char*[N];
for (i = 0; i < N; i++) {
quickSortSortedStrings[i] = strings[i];
}
COMPARE_ELEMENTS_COUNT = 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;
}
}
if (i == N) {
printf("correct sorting\n");
}
printf("%d ms / %d elements\n", t2 - t1, N);
printf("CompareElements() calls: %d\n", COMPARE_ELEMENTS_COUNT);
return 0;
}
