Categories
Geeky

Artificial QuickSort

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

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.