[ ngladov1 @ 18.11.2009. 16:28 ] @
Pozdrav svima!
Skinuo sam program u c-u koji radi sve vrste sortiranja. Program sortira 3000 elemenata te računa broj koraka i vrijeme potrebno da obavi sortiranje. Prvo radi sortiranje na sortiranom polju i vrši mjerenje, a zatim na random (nesortiranom) polju. Mene sad samo zanima da li je potrebno više koraka za sortiranje već sortiranog polja ili random polja. Prema tome što program ispisuje, manje je koraka potrebno za nesortirano polje. Po meni je logično suprotno, al možda sam u krivu, stoga me zanima vaše mišljenje!

Ispis izgleda ovako:

http://i46.tinypic.com/qqof21.jpg

[ EArthquake @ 18.11.2009. 20:18 ] @
koliko ja znam merge sort radi u najmanje koraka kada treba da sortira niz koji je vec sortiran
nesto mi tu nije uredu , osim ako taj niz u pocetnu nije sortiran naopako :)
[ mmix @ 18.11.2009. 20:43 ] @
Ma nije to jedino sumnjivo ovde. 1,3 miliona koraka? i u svim slucajevima 1000ms. ja bi reko da nesto nije u redu sa metrikom
[ EArthquake @ 19.11.2009. 07:56 ] @
lol da, a i uzasno je mali uzorak da bi se videla prava razlika

nadji bolji primer :)

[ ngladov1 @ 19.11.2009. 11:58 ] @
Ovo je program koji sam skinuo. Ne mogu naći direktnu stranicu, pa sam ga ovdje uplodao:

http://www.speedyshare.com/fil...76/Bubble__Se1631908182003.zip

U programu se može mjenjati ta velicina polja. Sada je postavljeno na #define MAX 1000 (471. linija koda), znači 1000 elementa, a ako treba može i više.

Mene samo zanima za merge i heap sort, da li je ispis tog programa u redu? Unaprijed se zahvaljujem
[ nikitaGradov @ 21.11.2009. 09:55 ] @
Citat:
ngladov1: Ovo je program koji sam skinuo. Ne mogu naći direktnu stranicu, pa sam ga ovdje uplodao:

http://www.speedyshare.com/fil...76/Bubble__Se1631908182003.zip

U programu se može mjenjati ta velicina polja. Sada je postavljeno na #define MAX 1000 (471. linija koda), znači 1000 elementa, a ako treba može i više.

Mene samo zanima za merge i heap sort, da li je ispis tog programa u redu? Unaprijed se zahvaljujem


int i;
int *orig = malloc(sizeof(*orig) * MAX);

// Fill original array
for (i = 0; i < MAX; i++)
orig = rand();

// Test with sorted array NETACNO: OVO JE TEST SA SLUCAJNIM VRIJEDNOSTIMA NIZA
printf("Testing with sorted %d element array\n", MAX);
test("bubble sort", srtBubble, orig, 1);
test("selection sort", srtSelection, orig, 1);
test("insertion sort", srtInsertion, orig, 1);
test("heap sort", srtHeap, orig, 1);
test("merge sort", srtMerge, orig, 1);
test("radix sort", srtRadix, orig, 1);
test("lib quicksort", srtLibQuickSort,orig, 1);
test("recursive quicksort", srtQuickSort, orig, 1);
test("better quicksort",srtBetterQuickSort, orig, 1);

// Test with unsorted array NETACNO: OVO JE TEST SA, PRETHODNO, SORTIRANIM VRIJEDNOSTIMA NIZA
printf("\nTesting with random %d element array\n", MAX);
test("bubble sort", srtBubble, orig, 0);
test("selection sort", srtSelection, orig, 0);
test("insertion sort", srtInsertion, orig, 0);
test("heap sort", srtHeap, orig, 0);
test("merge sort", srtMerge, orig, 0);
test("radix sort", srtRadix, orig, 0);
test("lib quicksort", srtLibQuickSort,orig, 0);
test("recursive quicksort", srtQuickSort, orig, 0);
test("better quicksort",srtBetterQuickSort, orig, 0);

Ako malo bolje pogledas, autoru se potkrala greska u komentarima, odnosno, napravio je gresku u ispisu redosleda testiranja: PRVO se testira niz sa slucajnim vrijednostima, pa tek onda sa SORTIRANIM. Zamijeni mjesta funkcijama printf(), pa ces dobiti pravi rezultat.
[ ngladov1 @ 21.11.2009. 18:18 ] @
Puno hvala za ovo, činilo mi se da je nešto sumnjivo al nisam bio 100% siguran!