Brzo sortiranje

[Shadowman]

TomK kaže:
Dakle, cini se da se shadowmanov algoritam ponasa bolje, osim u slucaju kad su svi elementi u array-u nulle, gdje je bizz-ov algoritam daleko superiorniji.

Ovo je sasvim logično, jer kod ovakvog inputa sam quicksort algoritam pravi najgori mogući split, dijeli niz na prazan, pivot i sve ostalo.

bizz, zašto ne bi napravio jedan pass kroz array i našao najveći broj. Onda možeš preskočiti sve bits do najvišeg bita najvećeg broja. Na primjer, najveći broj u nizu je 2^20. Odmah možeš početi s dvadesetim bitom, a sve ostale preskočiš.

[bizz]

Novi BizzSort je tu. Ispravljene su greske u algoritmu i algoritam je optimiziran (Cunac). Evo rezultata uz istovjetan input i ispisivanje prvih 10 i zadnjih 10 elemenata sortiranog niza:


Generate array[8000000] times
--------------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 0
Milliseconds : 971

Sort array times (quicksort)
----------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 6
Milliseconds : 349

Sort array times (bizzsort)
----------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 5
Milliseconds : 858

31
455
520
799
1446
1535
1538
1643
1801
1836
----------------------
2147449880
2147450164
2147450298
2147450418
2147450517
2147450575
2147450681
2147450724
2147450739
2147450814



Generate array[8000000] times
--------------------
In kernel mode:
Seconds : 0
Milliseconds : 10

In user mode :
Seconds : 0
Milliseconds : 941

Sort array times (quicksort)
----------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 6
Milliseconds : 419

Sort array times (bizzsort)
----------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 5
Milliseconds : 838

223
287
548
740
783
1048
1268
1679
1771
1844
----------------------
2147449636
2147449810
2147449897
2147449905
2147449980
2147450039
2147450136
2147450174
2147450190
2147450466


Generate array[8000000] times
--------------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 0
Milliseconds : 981

Sort array times (quicksort)
----------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 6
Milliseconds : 379

Sort array times (bizzsort)
----------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 5
Milliseconds : 848

471
642
868
1003
1009
1151
1530
1545
1558
1641
----------------------
2147449876
2147449907
2147449941
2147450102
2147450137
2147450142
2147450230
2147450789
2147450835
2147450850



Generate array[16000000] times
--------------------
In kernel mode:
Seconds : 0
Milliseconds : 20

In user mode :
Seconds : 1
Milliseconds : 932

Sort array times (quicksort)
----------------
In kernel mode:
Seconds : 0
Milliseconds : 20

In user mode :
Seconds : 13
Milliseconds : 539

Sort array times (bizzsort)
----------------
In kernel mode:
Seconds : 0
Milliseconds : 10

In user mode :
Seconds : 12
Milliseconds : 337

49
103
191
228
259
282
442
464
606
745
----------------------
2147450049
2147450150
2147450287
2147450362
2147450444
2147450559
2147450611
2147450621
2147450728
2147450752


Generate array[16000000] times
--------------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 1
Milliseconds : 952

Sort array times (quicksort)
----------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 13
Milliseconds : 349

Sort array times (bizzsort)
----------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 12
Milliseconds : 287

35
44
92
99
208
237
315
487
524
662
----------------------
2147450153
2147450233
2147450256
2147450321
2147450373
2147450507
2147450556
2147450740
2147450758
2147450876


Generate array[16000000] times
--------------------
In kernel mode:
Seconds : 0
Milliseconds : 20

In user mode :
Seconds : 1
Milliseconds : 942

Sort array times (quicksort)
----------------
In kernel mode:
Seconds : 0
Milliseconds : 10

In user mode :
Seconds : 13
Milliseconds : 479

Sort array times (bizzsort)
----------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 12
Milliseconds : 367

134
171
245
405
443
475
476
494
510
625
----------------------
2147449788
2147449848
2147449899
2147449918
2147449972
2147450321
2147450577
2147450579
2147450673
2147450853

[bizz]

Kod za testiranje:

#include <iostream>
#include <stdlib.h>
using namespace std;

#include "windows.h"
#include "process.h"
#include "stdio.h"
#include "time.h"

#define SIZE 8000000

void quicksort(UINT * a, UINT n)
{
	if(n>3)
	{
		UINT n2=n/2;
		UINT n3=n-1;
		if((a[0]<a[n2] && a[n2]<=a[n3]) || (a[0]>a[n2] && a[n2]>=a[n3]))
		{
			UINT temp=a[0];
			a[0]=a[n2];
			a[n2]=temp;
		}
		else
		if((a[0]<a[n3] && a[n3]<a[n2]) || (a[0]>a[n3] && a[n3]>a[n2]))
		{
			UINT temp=a[0];
			a[0]=a[n3];
			a[n3]=temp;
		}
		UINT low=1, high=n3;
		while(true)
		{
			for(;a[low]<a[0];low++);
			for(;high && a[high]>=a[0];high--);
			if(low>high)
				break;
			UINT temp=a[low];
			a[low]=a[high];
			a[high]=temp;
		}
		UINT temp=a[0];
		a[0]=a[high];
		a[high]=temp;
		quicksort(a, high);
		quicksort(a+high+1, n-high-1);
	}
	else
	if(n==3)
	{
		if(a[0]>a[1])
		{
			UINT temp=a[0];
			a[0]=a[1];
			a[1]=temp;
		}
		if(a[1]>a[2])
		{
			UINT temp=a[2];
			a[2]=a[1];
			a[1]=temp;
		}
		if(a[0]>a[1])
		{
			UINT temp=a[0];
			a[0]=a[1];
			a[1]=temp;
		}
	}
	else
	if(n==2 && a[0]>a[1])
	{
		UINT temp=a[0];
		a[0]=a[1];
		a[1]=temp;
	}
}


class BizzSort
{
	void sort( UINT* data, UINT len, UINT flag )
	{
		UINT head = 0, tail = len, swap;

		while( head < tail )
		{
			if( data[head] & flag )
			{
				while( --tail > head )
				{
					swap = data[tail];

					if(! (swap & flag) )
					{
						data[tail] = data[head];

						data[head++] = swap;

						break;
					}
				}
			}
			else
				head++;
		}

		if( flag >>= 1 )
		{
			if( head > 3 )
			{
				sort( data, head, flag );
			}
			else switch( head )
			{
				case 3:

				swap = data[0];

				if( swap > data[1] )
				{
					data[0] = data[1];

					data[1] = swap;
				}
				else
					swap = data[1];

				if( swap > data[2] )
				{
					data[1] = data[2];

					data[2] = swap;
				}
				else
					break;

				case 2:
                      
				swap = data[0];
                        
				if( swap > data[1] )
				{
					data[0] = data[1];

					data[1] = swap;
				}
			}
                
			if( (len-tail) > 3 )
			{
				sort( data+head, len-tail, flag );
			}
			else switch( (len-tail) )
			{
				case 3:

				swap = data[head];

				if( swap > data[head+1] )
				{
					data[head] = data[head+1];

					data[head+1] = swap;
				}
				else
					swap = data[head+1];
                       
				if( swap > data[head+2] )
				{
					data[head+1] = data[head+2];

						data[head+2] = swap;
				}
				else
					break;

				case 2:

				swap = data[head];

				if( swap > data[head+1] )
				{
					data[head] = data[head+1];

						data[head+1] = swap;
				}
			}
		}
	}

public:

	void normal( UINT* data, UINT len )
	{
		sort( data, len, 0x80000000 );
	}

	UINT unique( UINT* data, UINT len )
	{
		sort( data, len, 0x80000000 );

		UINT ret = 1;

		for( UINT i=1; i<len; i++ )
		{
			if( data[i] != data[ret-1] )
			{
				data[ret++] = data[SIZE-i-1];
			}
		}

		return ret;
	}
};

unsigned __stdcall GenerateArrayThreadFunc(void* pArguments);
unsigned __stdcall SortArrayThreadFunc(void* pArguments);
unsigned __stdcall SortArrayThreadFuncEx(void* pArguments);
void  PrintTimes(FILETIME *, FILETIME *);

BizzSort bizz;

int main()
{
	HANDLE hThread;
	UINT *pIntArray = 0;
	UINT *pIntArray2 = 0;
	FILETIME creationTime, exitTime, kernelTime, userTime; 

	pIntArray = new UINT[SIZE];
	pIntArray2 = new UINT[SIZE];

	hThread = (HANDLE) _beginthreadex(NULL, 0, &GenerateArrayThreadFunc, (void *) pIntArray, 0, NULL);
	WaitForSingleObject(hThread, INFINITE);
	GetThreadTimes(hThread,&creationTime, &exitTime, &kernelTime, &userTime);
	printf("Generate array[%d] times\n", SIZE);
	printf("--------------------\n");
	PrintTimes(&kernelTime, &userTime);	
	
	memcpy( pIntArray2, pIntArray, SIZE*sizeof(UINT) );

	hThread = (HANDLE) _beginthreadex(NULL, 0, &SortArrayThreadFunc, (void *) pIntArray, 0, NULL);
	WaitForSingleObject(hThread, INFINITE);
	GetThreadTimes(hThread,&creationTime, &exitTime, &kernelTime, &userTime);
	printf("Sort array times (quicksort)\n");
	printf("----------------\n");
	PrintTimes(&kernelTime, &userTime);

	hThread = (HANDLE) _beginthreadex(NULL, 0, &SortArrayThreadFuncEx, (void *) pIntArray2, 0, NULL);
	WaitForSingleObject(hThread, INFINITE);
	GetThreadTimes(hThread,&creationTime, &exitTime, &kernelTime, &userTime);
	printf("Sort array times (bizzsort)\n");
	printf("----------------\n");
	PrintTimes(&kernelTime, &userTime);

	for( int i=0; i<10; i++ )
	{
	  cout << pIntArray2[i] << endl;
    }
    
    cout << "----------------------" << endl;
    
	for( int i=SIZE-10; i<SIZE; i++ )
	{
	  cout << pIntArray2[i] << endl;
    }

	delete [] pIntArray2;
	delete [] pIntArray;
	
	return 0;
}

void  PrintTimes(FILETIME *kernelTime, FILETIME *userTime)
{
	SYSTEMTIME systemTime;
	FileTimeToSystemTime(kernelTime, &systemTime);
	printf("In kernel mode:\n");
	printf("Seconds       : %d\n", systemTime.wSecond);
	printf("Milliseconds  : %d\n\n", systemTime.wMilliseconds);

	FileTimeToSystemTime(userTime, &systemTime);
	printf("In user mode  :\n");
	printf("Seconds       : %d\n", systemTime.wSecond);
	printf("Milliseconds  : %d\n\n", systemTime.wMilliseconds);
}

unsigned __stdcall GenerateArrayThreadFunc(void* pArguments)
{
	UINT *pIntArray = (UINT *) pArguments;

	// ovdje code koji generira vrijednosti u array-u (pIntArray)

	srand(time(NULL));

	for(int i = 0; i < SIZE; i++ )
	{
		pIntArray[i] = (rand()<<16) + rand();
	}

	return 0;
}

int cmp_u32(const void* e1, const void* e2)
{
    const UINT* p1 = (const UINT*)e1;
    const UINT* p2 = (const UINT*)e2;
    if(*p1 == *p2)
        return 0;
    else if(*p1 < *p2)
        return -1;
    else
        return 1;
}

unsigned __stdcall SortArrayThreadFunc(void* pArguments)
{
	UINT *pIntArray = (UINT *) pArguments;

	// ovdje code koji sortiara array (pIntArray)

	quicksort(pIntArray, SIZE);
//    std::qsort(pIntArray, SIZE, sizeof(UINT), cmp_u32);

	return 0;
}

unsigned __stdcall SortArrayThreadFuncEx(void* pArguments)
{
	UINT *pIntArray = (UINT *) pArguments;

	// ovdje code koji sortiara array (pIntArray)

	bizz.normal(pIntArray, SIZE);

	return 0;
}