People, there is a new sorting algorithm in town.. well it’s not that new it’s
been here since 2004 but I’ve just heard about it
It’s called the “Artificial
QuickSort algorithm” and it goes like:
#include <stdio.h> #include <windows.h>
int array[20000000];
int Rnd(int x1, int x2) {
int x = x2 – x1 + 1;
int m = (rand() % x) + x1;
int n = (rand() % x) + x1;
m = (32000*m + n) % x;
return m;
}
void ArtificialQuickSort(int array[], int nor) {
int levi[256];
int desni[256];
int index = 0; int i = 0; int j = 0;
int left = 0; int right = 0; int meja = 0;
int left1 = 0; int right1 = 0;
int temp1 = 0; int temp2 = 0; int temp = 0;
left = 0; right = nor-1;
while (left < right){
if (array[left] > array[right]) {
temp = array[left];
array[left] = array[right];
array[right] = temp;
}
left++; right–;
}
index = 0; levi[index] = 0; desni[index] = nor-1;
while ( index >= 0 ) {
left = levi[index]; right = desni[index];
temp = right – left;
if ( temp > 15 ) {
// Main section of ArtificialQuickSort ——————————————-
temp1 = array[left];
for ( j = left+1; j <= right; j++) {
temp2 = array[j];
if ( temp2 < temp1) {
meja = ( temp1 + temp2 + 1 ) >> 1;
if ( array[ (left + right) >> 1 ] > meja ) {
meja = array[ (left + right) >> 1 ];
}
left1 = left;
right1 = right;
for (;;) {
while ( array[right1] >= meja ) right1–;
while ( array[left1] < meja ) left1++;
if (left1>right1) break;
temp = array[right1];
array[right1–] = array[left1];
array[left1++] = temp;
}
desni[index] = –left1;
levi[++index] = ++right1;
desni[index] = right;
goto labelcritticall5;
}
temp1=temp2;
}
// End of the main section of ArtificialQuickSort ——————————–
} else {
if ( temp != 0 ) {
// InsertionSort ———————————————————–
temp1 = array[left];
for ( i = left+1; i <= right; ++i ) {
temp2 = array[i];
if ( temp1 > temp2 ) {
array[i] = temp1;
for ( j = i-1; j > left; ) {
temp = array[j-1];
if ( temp > temp2 ) array[j–] = temp; else break;
}
array[j] = temp2;
} else {
temp1 = temp2;
}
}
// End of InsertionSort —————————————————–
}
}
index–;
labelcritticall5:;
}
}
int main() {
int i,n, timtim;
int NumberOfRec = 20000000;
printf (“\n Artificial QuickSort\n\n”);
printf (” Number of records = %d\n\n”,NumberOfRec);
for (n=10000000; n>=0; n/=10) {
printf (” Data = Rnd[%9d,%9d] … “,-n,n);
if (n==0) {
for (int i=0; i
array[i] = 0;
}
} else {
for (i=0; i<NumberOfRec; i++) {
array[i] = Rnd(1,n)-Rnd(1,n);
}
}
printf (“Sorting … “);
timtim = GetTickCount();
ArtificialQuickSort(array, NumberOfRec);
printf (“Elapsed = %5d ms\n”, GetTickCount()-timtim);
if (n==0) break;
}
system(“pause”);
return 0;
}
Really good job, I don’t know why they never taught us this algorithm in college