Brzo sortiranje

[bizz]

Shadowman kaže:
Znači da ti je veći unsigned long int. Ali, nema veze. Ipak ostaje da je to jedan broj, koji nema veze s veličinom niza, koji se sortira. Da bi sortirao linearno moraš brojati svaki od brojeva koji se može pojaviti. Znači, ako imaš više od 4096 RAZLIČITIH brojeva za sortirati, nema teoretske šanse da to napraviš

Pa stos je u tome da ovaj sort broji svaki od brojeva koji se moze pojaviti, ali na jedan specifican nacin.

Nacin na koji to vi zamisljate je problematican jer je potrebno alocirati veliko polje, 2 na 32-u ili dva na 64-u, a to je prakticki nemoguce. Pogledaj jos jedanput, odnosno probaj rezerviratil polje od recimo 1.000.000 random brojeva u rasponu koji to int ili unsigned int dozvoljava i uvjeri se da sort radi.

[Shadowman]

Pošto insistiraš na tome da radi, probao sam. I nije čak izbacio ni iste brojeve, a kamoli da ih je sortirao. Na primjer izbacio je 77 nula, dvije jedinice, a najmanji broj u inputu bio je 1000048663. U principu, malo je vjerovatno da se ikoji broj ponovio u inputu, a u tvom outputu svaki broj se ponavlja puno puta. probao sam tražiti specifične brojeve iz inputa u tvom outputu i nema ih.

[bizz]

Imas pravo. Ideja je bila dobra, ali matematika je ipak neumoljiva. Bye.

[Shadowman]

bizz kaže:
Ideja je bila dobra, ali matematika je ipak neumoljiva.

Eto vidiš kako je život matematičara težak.

[bizz]

Shadowman kaže:
Eto vidiš kako je život matematičara težak.

Uopce ti ne zavidim

[Shadowman]

Evo funkcija za linearno sortiranje. size je veličina niza, a elementi niza su ograničeni na nenegativne integere manje od max.

void linear_sort(int * a, int size, int max)
{
	int * count=new int[max];
	for(int i=0; i<max; count[i++]=0);
	for(int i=0; i<size; count[a[i++]]++);
	for(int i=0, current=0; i<max; i++)
		for(; count[i]--; a[current++]=i);
}

[TomK]

U svome rjesenju koristis 4 for petlje, koje sa stanovista performansi i nisu bas najoptimalnije sredstvo za rjesavanje problema, a narocito ukoliko je broj elemenata u array-u ogroman.

Pitanje je dali se isti algoritam (ili neki drugi) moze napisati da radi optimalnije?

To je upravo bila ideja iza programa koji ce mjeriti koliko je vremena potrosio neki algoritam na obavljanje posla. Za takvo sto je dakako potreban prikladan array ciji su elementi slucajno rasporedjeni i razliciti. Taj algoritam je u sebi vec izazov napisati.

No, zbog nekog razloga, svaka stvar na ovome forumu koja je izvan nekog trivijalnog ili teorijskog (matematickog) nivoa, ne moze pobuditi interes kod forumasa. Sto je razlog tomu ne znam, ali znam da sam dobro na putu da prestanem biti aktivan sudionik ovdje.

Lijepi pozdravi,

[Shadowman]

Četiri petlje znače četiri puta n. A to je linearno. Drugo je ako su nested. Jedna je, ali ako malo bolje pogledaš, vidjećeš da se za svaki element, unutrašnja petlja izvrši jednom, a to znači da je linearno. Nije ono tvoje prošlo nezapaženo. Napisaću i ja svoju verziju, ali daj malo vremena. Imam zadaću za sutra. Ustvari, morao bih sad ići pisati, a ja gubim vrijeme na forumu. Jesi li mislio na bilo kakve integere ili u odreženom rasponu, kao što je prvobitno bilo zamišljeno. Zašto insistiraš da su svi različiti? Kao dodatni dio zadatka?

[TomK]

Zapravo, ono sto sam zelio je da ovoj diskusiji o sortiranju dam jednu novu dimenziju, a ta je da doista, na egzaktan nacin testiramo razlicite tehnike sortiranja, ali i njihove implementacije. Nedavno nam je predavanje drzao jedan programer koji pise sah programe zadnjih dvadesetak godina, i on je nekoliko puta naglasio kako su for petlje zadnje sto jedan sah program treba koristiti (profesionalni sah programi ih gotovo i ne koriste), upravo zbog svojih performansi, i da postoje drugi nacini kako se odredjeni problemi mogu rijesiti bez for petlji (on je for petlje nazvao "rjesenje za ljencine" jer ih je tako jednostavno koristiti).
Dakle dali cemo testirati array koji ima sve vrijednosti razlicite, dali cemo koristiti ovaj ili onaj algoritam, mislim da uopce nije toliko ni vazno, jer ono sto je bitno je da zajedno vidimo kako je neki algoritam najbolje implementirati. Koje je jezicne konstrukcije nabolje koristiti? Gdje su mjesta koja su najveci konzumenti vremena? Mogu li se ta "uska grla" rijesiti? Jedini razlog zasto bi array trebao biti ogroman i po mogucnsti tezak za sortiranje je taj sto je vremenska rezolucija koju mozemo mjeriti 10 ms. Dakle, trebali bi doista zaposliti masinu kako bi vidjeli razlike u performansama.

Mislim da bi to doista bilo zanimljivo vidjeti. A zapravo, sve je tu. Jedino nedostaju algoritmi o kojima se toliko raspravljalo na forumu zadnjih dana.

[cunac]

TomK kaže:
Zapravo, ono sto sam zelio je da ovoj diskusiji o sortiranju dam jednu novu dimenziju, a ta je da doista, na egzaktan nacin testiramo razlicite tehnike sortiranja, ali i njihove implementacije. Nedavno nam je predavanje drzao jedan programer koji pise sah programe zadnjih dvadesetak godina, i on je nekoliko puta naglasio kako su for petlje zadnje sto jedan sah program treba koristiti (profesionalni sah programi ih gotovo i ne koriste), upravo zbog svojih performansi, i da postoje drugi nacini kako se odredjeni problemi mogu rijesiti bez for petlji (on je for petlje nazvao "rjesenje za ljencine" jer ih je tako jednostavno koristiti).

unroll petlji je opce poznata stvar no primjenjljiv je na petljama koje imaju mali i relativno predvidiv broj iteracija, pogotovo maksimum. Za petlje kojima je maksimum neka funkcija sa "nepredvidivim" rezultatima to nije primjenljvo.
Unroll vecinom radis u igrama kada se prolazi kroz dinamicke liste itd..

Sto se tice testiranja performansi, propusti program kroz profiler i onda gledaj gdje su mjesta koja trose najvise vremena. Samo mjerenje vremena izvrsavanja ti nece dati hint gdje su moguce optimizacije.

[math_baby]

TomK kaže:
Zapravo, ono sto sam zelio je da ovoj diskusiji o sortiranju dam jednu novu dimenziju, a ta je da doista, na egzaktan nacin testiramo razlicite tehnike sortiranja, ali i njihove implementacije. Nedavno nam je predavanje drzao jedan programer koji pise sah programe zadnjih dvadesetak godina, i on je nekoliko puta naglasio kako su for petlje zadnje sto jedan sah program treba koristiti (profesionalni sah programi ih gotovo i ne koriste), upravo zbog svojih performansi, i da postoje drugi nacini kako se odredjeni problemi mogu rijesiti bez for petlji (on je for petlje nazvao "rjesenje za ljencine" jer ih je tako jednostavno koristiti).
Dakle dali cemo testirati array koji ima sve vrijednosti razlicite, dali cemo koristiti ovaj ili onaj algoritam, mislim da uopce nije toliko ni vazno, jer ono sto je bitno je da zajedno vidimo kako je neki algoritam najbolje implementirati. Koje je jezicne konstrukcije nabolje koristiti? Gdje su mjesta koja su najveci konzumenti vremena? Mogu li se ta "uska grla" rijesiti? Jedini razlog zasto bi array trebao biti ogroman i po mogucnsti tezak za sortiranje je taj sto je vremenska rezolucija koju mozemo mjeriti 10 ms. Dakle, trebali bi doista zaposliti masinu kako bi vidjeli razlike u performansama.

Mislim da bi to doista bilo zanimljivo vidjeti. A zapravo, sve je tu. Jedino nedostaju algoritmi o kojima se toliko raspravljalo na forumu zadnjih dana.

Prestani pricati gluposti! Performanse algoritma se ne mjere tako da se uzme "stoperica" i onda izmjeri vrijeme trajanja izvrsavanja. Jer, time dobivamo samo brzinu izvrsavanja tog algoritma na toj i toj konkretnoj platformi, za te i te konkretne ulazne parametre.
Postoji cijela teorija koja iza toga stoji (i koju ti vjerojatno prezires zato sto je "teorija") koja govori kako se to radi. Brzina algoritma ne daje se ni u kakvim vremenskim jedinicama (jer se one mijenjaju kako se procesori i njihove brzine usavrsavaju). Umjesto toga, mjeri se broj elementarnih operacija koje algoritam mora izvrsiti. I pri tome se gleda asimptotsko ponasanje funkcije koja na osnovi velicine ulaznih podataka daje broj potrebnih elementarnih operacija.

Sve preporuke tipa "nemojte koristiti petlje", nemojte ovo, nemojte ono nemaju veze s mozgom. Procitaj neku knjigu koja se bavi analizom algoritama i shvati jedno: bez jako dobrog znanja matematike i statistike tu se nema sto traziti!

Najbolja literatura koju bih mogla preporuciti svakome koga problematika izracunavanja slozenosti algoritama zanima je ova knjiga Herberta Wilfa (koju mozete besplatno skinuti na ovom linku), kao i Knuthova trilogija "The art of computer programming" ili, recimo ova, vrlo popularna knjiga.

Izbijte sebi iz glave ideju da je moguce sastavljati kvalitetne algoritme (ili procjenjivati vrijeme izvrsavanja vec postojecih) bez teoretskog znanja (uglavnom matematickog) koje je opisano u gore navedenim knjigama!

Dizajn aplikacija je jedno, analiza algoritama nesto sasvim drugo!

math_baby

[lijencina]

TomK kaže:
Hajde ipak da stvari napravimo za nijansu zanimljivijim: Prosirimo zadatak tako da:

1) kreirate integer array odredjene velicine, i generirate njegove vrijednosti od kojih je svaka vrijednost razlicita od druge (dakle dvije vrijednosti se ne ponavljaju).

2) sortirajte array sto brze (algoritam sami izaberite).

Da bi ipak mogli testirati koliko su oba algoritma (generiranje i sortiranje) efektivni, evo mali program koji moze mjeriti vrijeme (10 ms rezolucija):

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

#define ARRAY_SIZE 4000000

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

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

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

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

	delete [] pIntArray;
}

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)
{
	int *pIntArray = (int *) pArguments;
	pIntArray = new int[ARRAY_SIZE];
	
	// ovdje code koji generira vrijednosti u array-u (pIntArray)

	return 0;
}

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

	// ovdje code koji sortiara array (pIntArray)

	return 0;
}

Dakle, array je velicine 4 MB, tako da pokriva gotovo sve integer vrijednosti. Ukoliko se to cini previse, moze se velicina i smanjiti, no mislim da ce se efikasnost algoritma bolje pokazati na vecim velicinama. Drugo, kao sto vidite, postoje dvije thread funkcije: Jedna za generiranje arraya (GenerateArrayThreadFunc) i jedna za sortiranje arraya (SortArrayThreadFunc). Tu treba doci vas code (u main funkkciji ne trebate dodavati nikakav code).
pIntArray predstavlja adresu arraya, i ne trebate niti alocirati niti brisati memoriju, jer ce to program uciniti za vas. Dakle u GenerateArrayThreadFunc je vec alocirana memorija, vase je da generirate vrijednosti i popunite array. Taj isti array ce te dobiti u SortArrayThreadFunc, i odmah mozete pristupiti sortiranju, Prrogram ce na kraju ispisati vrijeme koji je svaki od ova dva threda potrosio kako u kernel, tako i u user modu.
Program kompajlirajte sa multithreaded library.
Ukoliko nemate odgovarajuci kompajler, ostavite code na forumu, a onda cu ja to testirati i izvjestiti o rezultatima.
Nadam se da ce biti zanimljivo.

Imam prijedlog. A da povecas prioritet procesa i threada na real time critical sa SetPriorityClass() i SetThreadPriority() dok vrsis mjerenje inace ti drugi procesi mogu utjecati na rezultat. Naprimjer drugi proces prekine tvoj proces i izbrise ti razne nivoe cache-a u procesoru. Ne mora se dogoditi ali nije garantirano. Ovako bi to bilo manje vjerojatno.

Slican primjer za Java, mjerenje i thread priority:
http://java.ittoolbox.com/groups/gro...ava-l&i=369350

[lijencina]

Osim toga, ako koristite C++ uvijek mozete koristiti STL za razna sortiranja. Na taj nacin se sortiranje cesto svede na jednu liniju nesto kao:

MojePolje.sort();

MojePolje moze biti bilo sto sto ima definiran operator <= (ili jedan od tih, ne mogu se tocno sjetiti). na taj nacin je izuzetno lako sortirati int, char, long, float, double. A ako definiras operator sam, onda mozes sortirati bilo sta ukljuculuci strukture.

Cesto puno jednostavnije.

[cunac]

math_baby kaže:
Prestani pricati gluposti! Performanse algoritma se ne mjere tako da se uzme "stoperica" i onda izmjeri vrijeme trajanja izvrsavanja. Jer, time dobivamo samo brzinu izvrsavanja tog algoritma na toj i toj konkretnoj platformi, za te i te konkretne ulazne parametre.
Postoji cijela teorija koja iza toga stoji (i koju ti vjerojatno prezires zato sto je "teorija") koja govori kako se to radi. Brzina algoritma ne daje se ni u kakvim vremenskim jedinicama (jer se one mijenjaju kako se procesori i njihove brzine usavrsavaju). Umjesto toga, mjeri se broj elementarnih operacija koje algoritam mora izvrsiti. I pri tome se gleda asimptotsko ponasanje funkcije koja na osnovi velicine ulaznih podataka daje broj potrebnih elementarnih operacija.

Sve preporuke tipa "nemojte koristiti petlje", nemojte ovo, nemojte ono nemaju veze s mozgom. Procitaj neku knjigu koja se bavi analizom algoritama i shvati jedno: bez jako dobrog znanja matematike i statistike tu se nema sto traziti!

Najbolja literatura koju bih mogla preporuciti svakome koga problematika izracunavanja slozenosti algoritama zanima je ova knjiga Herberta Wilfa (koju mozete besplatno skinuti na ovom linku), kao i Knuthova trilogija "The art of computer programming" ili, recimo ova, vrlo popularna knjiga.

Izbijte sebi iz glave ideju da je moguce sastavljati kvalitetne algoritme (ili procjenjivati vrijeme izvrsavanja vec postojecih) bez teoretskog znanja (uglavnom matematickog) koje je opisano u gore navedenim knjigama!

Dizajn aplikacija je jedno, analiza algoritama nesto sasvim drugo!

math_baby

Nazalost vecina ljudi misli da je bitna optimizacija implementacije za postici brzinu (to su oni tipa ja pisem u ASM i to je super brzo, naravno nema veze sto je algoritam traljav ) ,a kljucno je izabrati/smisliti adekvatan algoritam za dati problem., optimizacija implementacije je za red velicine laksa za postizanje

[TomK]

Pa gledajte, cunac, i math_baby,

ja sam dao prijedlog kako bi mogli testirati performanse algoritma, koji, slozit cu se , nije idealan, ali jest nekakav, i sto je vrlo bitno, konkretan program koji bi to mogao i demonstrirati!!!

To sto ste vi dali kao odgovor na to je cista teorija od koje nitko nema nikakve koristi.

Dakle, ako ste vec toliko pametni da date negativnu ocjenu za moju ideju i konkretni program, onda izvolite, dajte vi konktretni program koji ce svatko moci copy-paste i testirati alogoritam na vas "puno bolji" nacin.

Sve dok to ne postavite na ovaj forum, sorry, ipak je sve sto pisete mlacenje prazne slame.

Lijepi pozdravi (u teoriji )

[TomK]

Imam prijedlog. A da povecas prioritet procesa i threada na real time critical sa SetPriorityClass() i SetThreadPriority() dok vrsis mjerenje inace ti drugi procesi mogu utjecati na rezultat. Naprimjer drugi proces prekine tvoj proces i izbrise ti razne nivoe cache-a u procesoru. Ne mora se dogoditi ali nije garantirano. Ovako bi to bilo manje vjerojatno.

Potpuno se slazem sa ovim sto si napisao. Radio sam neke testove vezane za cashe, i to je podrucje doista "granicno", dakle, veoma je upitno koliko mi kao programeri imamo utjecaj kako ce procesor tretirati cache memoriju.

Dakle, slazem se da bi test dao puno vjerodostojnije rezultate ukoliko bi se povecali prioriteti procesa i thread-ova.

Lijepi pozdravi,

[cunac]

TomK kaže:
Pa gledajte, cunac, i math_baby,

ja sam dao prijedlog kako bi mogli testirati performanse algoritma, koji, slozit cu se , nije idealan, ali jest nekakav, i sto je vrlo bitno, konkretan program koji bi to mogao i demonstrirati!!!

To sto ste vi dali kao odgovor na to je cista teorija od koje nitko nema nikakve koristi.

bas naprotiv, to je cista praksa. Da li si ikada isao optimizirati neki program koji ima 100K+ linija. Reci mi kako to radis, ja koristim profilere za frst cut i onda optimizaciju algoritma tj. po mogucnosti optimalne algoritme

Dakle, ako ste vec toliko pametni da date negativnu ocjenu za moju ideju i konkretni program, onda izvolite, dajte vi konktretni program koji ce svatko moci copy-paste i testirati alogoritam na vas "puno bolji" nacin.

Sve dok to ne postavite na ovaj forum, sorry, ipak je sve sto pisete mlacenje prazne slame.

Lijepi pozdravi (u teoriji )

Mozda da naucis prihvatiti kritiku kao nesto neosobno, to bi dosta pomoglo u raspravi.
Math ti je rekla kako se testira slozenost algoritma, koji dio nije bio jasan ?

[TomK]

Ma ti bi cunac ovako mogao jos 16 godina...

Kako ne shvacas da ovaj forum nije nikakva firma (pusti te price o 100k+ linija), nego mjesto gdje se razmjenjuje iskustva medju nama koji volimo programiranje, kao i code iz kojega se nesto moze nauciti.

Ja sam sa svojim malim primjerom, ako nista drugo, pokazao kako se moze mjeriti vrijeme koje thread koristi na windows platformi, i mislim da to nije glupo koristiti kao jedan od metoda za mjerenje efikasnosti koda, sto ne iskljucuje i neke naprednije tehnike optimatizacije, ali o tome ovdje nema niti mjesta niti publike za takvo sto.

Tvoji postovi, za razliku od mojih, su uvijek pokusaj negiranja tudjuh postova, bez ikakve prakticne vrijednosti, dakle, sa izuzetkom jednog ili dva posta, tvoji, a dobrim dijelom i math-ovi postovi nemaju nikakvu prakticnu i uporabnu vrijednost i vjerujem da ih nitko ne cita vise od jedan jedini puta, za razliku od nekih postova koji sadrze konkretan code, te kao takvi postaju zanimljivi svakom programeru koji se i sam dotice sa odredjenom problematikom.

Zato su tvoji postovi, ukljucujuci i ovaj zadnji, doista mlacenje prazne slame, koji ce biti zaboravljen jednakom brzinom kao sto je i procitan.

A te tvoje price o velikim projektima, mislim da bi konacno morao shvatiti da to uopce nije relevantno na ovakvom jednom forumu, i moderatori bi po mome misljenju trebali izbaciti vecinu tvojih postova jer nemaju nikave veze sa topicom, niti kakvu uporabnu vrijednost.

Lijepi pozdravi (u teoriji )

[bizz]

TomK kaže:
Kako ne shvacas da ovaj forum nije nikakva firma (pusti te price o 100k+ linija), nego mjesto gdje se razmjenjuje iskustva medju nama koji volimo programiranje, kao i code iz kojega se nesto moze nauciti.

U tu svrhu, prebacujem klasu LinearSort sa topica math_baby ovamo.

Shadowman, ova klase dokazuje da je moguce linearno sortirati podatke bez poznavanja podrucja u kojem su ulazni podaci.

#include <iostream.h>
#include <stdlib.h>
#include <time.h>

typedef unsigned int UINT;

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

		for( UINT i=0; i<len; i++ )
		{
			if( data[head] & flag )
			{
				swap = data[--tail];

				data[tail] = data[head];

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

		flag >>= 1;

		if( flag )
		{
			if( head )
				sort( data, head, flag );

			if( len-tail )
				sort( data+head, len-tail, flag );
		}
	}

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[i];
			}
		}

		return ret;
	}
};

int main()
{
	const UINT size = 1000000;

	UINT* data = new UINT[size];

	srand( time(NULL) );

	for( UINT i=0; i<size; i++ )
	{
		data[i] = rand()*rand();
	}

	LinearSort sort;

	sort.normal( data, size );

	for( i=0; i<size; i++ )
	{
		cout << data[i] << endl;
	}

	delete data;

	return 0;
}

[TomK]

Evo bizz-ov code integriran sa test programom. Masina na koju sam testirao je Celeron 500 Mhz, 192 MB Ram. Velicina arraya je 1.000.000

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

#define SIZE 1000000

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

		for( UINT i=0; i<len; i++ )
		{
			if( data[head] & flag )
			{
				swap = data[--tail];

				data[tail] = data[head];

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

		flag >>= 1;

		if( flag )
		{
			if( head )
				sort( data, head, flag );

			if( len-tail )
				sort( data+head, len-tail, flag );
		}
	}

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[i];
			}
		}

		return ret;
	}
};

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

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

	pIntArray = 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 times\n");
	printf("--------------------\n");
	PrintTimes(&kernelTime, &userTime);	

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

	delete [] pIntArray;
}

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() * rand();
	}

	return 0;
}

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

	// ovdje code koji sortiara array (pIntArray)

	LinearSort sort;
	sort.normal(pIntArray, SIZE);

	return 0;
}

A ovo je rezultat:

Generate array times
--------------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 0
Milliseconds : 200

Sort array times
----------------
In kernel mode:
Seconds : 0
Milliseconds : 0

In user mode :
Seconds : 3
Milliseconds : 364

Evo , bizz je sada svima uputio izazov. Moze li netko moze istu stvar napraviti da radi efikasnije? Ili nesto unaprijediti u bizz-ovom algoritmu?

Lijepi pozdravi

P.S. Testirao sam algoritam na malim velicinama (SIZE = 200) i ispisivao rezultat, i algoritam radi bez greske.