Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Heap i Merge sortiranje, sortiran/nesortiran niz

[es] :: Art of Programming :: Heap i Merge sortiranje, sortiran/nesortiran niz

[ Pregleda: 3387 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

ngladov1

Član broj: 117666
Poruke: 20
*.adsl.net.t-com.hr.



Profil

icon Heap i Merge sortiranje, sortiran/nesortiran niz18.11.2009. u 16:28 - pre 174 meseci
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

 
Odgovor na temu

EArthquake

Član broj: 20684
Poruke: 884
*.adsl.eunet.rs.



+67 Profil

icon Re: Heap i Merge sortiranje, sortiran/nesortiran niz18.11.2009. u 20:18 - pre 174 meseci
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 :)
 
Odgovor na temu

mmix
Miljan Mitrović
Profesorkin muz
Passau, Deutschland

SuperModerator
Član broj: 17944
Poruke: 6041



+4631 Profil

icon Re: Heap i Merge sortiranje, sortiran/nesortiran niz18.11.2009. u 20:43 - pre 174 meseci
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
Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan, sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv… - Z.Đinđić
 
Odgovor na temu

EArthquake

Član broj: 20684
Poruke: 884
*.adsl.eunet.rs.



+67 Profil

icon Re: Heap i Merge sortiranje, sortiran/nesortiran niz19.11.2009. u 07:56 - pre 174 meseci
lol da, a i uzasno je mali uzorak da bi se videla prava razlika

nadji bolji primer :)

 
Odgovor na temu

ngladov1

Član broj: 117666
Poruke: 20
*.adsl.net.t-com.hr.



Profil

icon Re: Heap i Merge sortiranje, sortiran/nesortiran niz19.11.2009. u 11:58 - pre 174 meseci
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
 
Odgovor na temu

nikitaGradov
Beograd

Član broj: 223576
Poruke: 206
*.ppp.panet.co.yu.



+3 Profil

icon Re: Heap i Merge sortiranje, sortiran/nesortiran niz21.11.2009. u 09:55 - pre 174 meseci
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.
Programming is fun, but writing good software is hard ...
 
Odgovor na temu

ngladov1

Član broj: 117666
Poruke: 20
*.adsl.net.t-com.hr.



Profil

icon Re: Heap i Merge sortiranje, sortiran/nesortiran niz21.11.2009. u 18:18 - pre 174 meseci
Puno hvala za ovo, činilo mi se da je nešto sumnjivo al nisam bio 100% siguran!
 
Odgovor na temu

[es] :: Art of Programming :: Heap i Merge sortiranje, sortiran/nesortiran niz

[ Pregleda: 3387 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.