[es] - Poredjenje sortiranja

ksrele
Programer - informatičar
Gold Drink D.O.O. Subotica
Subotica

Član broj: 14253
Poruke: 1642
*.dynamic.isp.telekom.rs.

ICQ: 66444502

+47 Profil

Poredjenje sortiranja

^{12.12.2010. u 21:09 - pre 162 meseci}

Pozdrav svima.
Zamolila me jedna koleginica da joj pomognem oko jednog zadatka u C jeziku. Moram priznati da sam ja JAAAAKO davno radio u C jeziku i to sam tada zesce brkao C i C++ (mislio sam da je to jedno te isto) i tek sada vidim da to tako ne ide... :)
Nego, da predjem ja na stvar.
Dobila je zadatak da 4 (zadata) algoritma za sortiranje prilagodi tako da se mogu uporediti po:
1. vremenu potrebnom za izvrsavanje
2. broju potrebnih "promena" (swaps)
3. broju potrebnih uporedjivanja

Pri tom, je jos potrebno prosiriti algoritme da mogu da rade i sa nekim drugim tipovima podatak i da mogu da sortiraju i u rikverc.

E sad, znaci ona je dobila ciste algoritme u jednom smeru bez ikakvog merenja a ja sam joj ugradio merenje i prebrojavanje i rikverc sortiranje.
Od vas bi zeleo da mi to proverite da li je OK sto sam uradio, jer ja sam nemam pojma gde da se tacno broje ta poredjenja i menjanje clanova.

Evo sada jedan po jedan algoritam u CODE blokovima (radi lakseg pregleda) a ceo kod je u prilozenom fajlu.

Code (c):

static void bubble_sort(int arr[], int length)

{

     int i, swapped;

     do

     {

          swapped = 0;

          if (bubble_rev_dir)

          {

               for (i = 1; i < length; i++)

               {

                    bubble_comp_count++;

                    if (arr[i - 1] < arr[i])

                    {

                         swap(&arr[i - 1], &arr[i]);

                         bubble_swap_count++;

                         swapped = 1;

                    }

               }

          }

          else

          {

               for (i = 1; i < length; i++)

               {

                    bubble_comp_count++;

                    if (arr[i - 1] > arr[i])

                    {

                         swap(&arr[i - 1], &arr[i]);

                         bubble_swap_count++;

                         swapped = 1;

                    }

               }

          }

     } while (swapped);

}

Code (c):

static void insertion_sort(int arr[], int length) {

     int i, j, key;

     if (ins_rev_dir)

          {

               for (i = 1; i < length; i++) {

                    key = arr[i];

                    j = i - 1;

                    ins_comp_count++;

                    while (j >= 0 && key > arr[j]) {

                         ins_swap_count++;

                         arr[j + 1] = arr[j];

                         j--;

                    }

                    arr[j + 1] = key;

               }

          }

     else

          {

               for (i = 1; i < length; i++) {

                    key = arr[i];

                    j = i - 1;

                    ins_comp_count++;

                    while (j >= 0 && key < arr[j]) {

                         ins_swap_count++;

                         arr[j + 1] = arr[j];

                         j--;

                    }

                    arr[j + 1] = key;

               }

          }

}

Code (c):

static void selection_sort(int arr[], int length) {

     int i, j, min, max;

     if (sel_rev_dir)

     {

          for (i = 0; i < length - 1; i++) {

               max = i;

               for (j = i + 1; j < length; j++)

                    {

                    sel_comp_count++;

                    if (arr[j] > arr[max])

                         max = j;

                    }

               swap(&arr[i], &arr[max]);

               sel_swap_count++;

          }

     }

     else

     {

          for (i = 0; i < length - 1; i++) {

               min = i;

               for (j = i + 1; j < length; j++)

                    {

                    sel_comp_count++;

                    if (arr[j] < arr[min])

                         min = j;

                    }

               swap(&arr[i], &arr[min]);

               sel_swap_count++;

          }

     }

}

Code (c):

static void merge(int arr[], int l, int m, int r) {

     int *tmp = (int *) malloc(sizeof(int) * (m - l + 1));

     int i, j = 0, k = m + 1;

     /* kopiere arr[l..m] in ein temporaeres Array */

     for (i = l; i <= m; i++)

          tmp[j++] = arr[i];

     /* vergleiche die Eintraege des temp. Arrays mit den Eintraegen arr[m+1..r] */

     i = l;

     j = 0;

     while (i < k && k <= r)

          {

          merge_comp_count++;

          if (tmp[j] <= arr[k])

               {

                    arr[i++] = tmp[j++];

                    merge_swap_count++;

               }

          else

               {

                    arr[i++] = arr[k++];

                    merge_swap_count++;

               }

          }

     /* kopiere eventuelle vorhandene Eintraege des temp. Arrays nach arr */

     while (i < k)

          {

               arr[i++] = tmp[j++];

               merge_swap_count++;

          }

     free(tmp);

}

/* merge-sort */

static void merge_sorter(int arr[], int l, int r) {

     int m = (l + r) / 2;

     /* arr[l..r] hat min. zwei Elemente <=> l < r */

     if (l < r) {

          /* sortiere ersten Teil */

          merge_sorter(arr, l, m);

          /* sortiere zweiten Teil */

          merge_sorter(arr, m + 1, r);

          /* Fuege sortierte Teile zusammen */

          merge(arr, l, m, r);

     }

}

/* Wrapper für mergesorter */

static void merge_sort(int arr[], int n) {

     merge_sorter(arr, 0, n - 1);

}

P.S.
Kao sto primecujete, komentari su na nemackom (kojeg ja ne znam) a ona mi je prevela kompletan tekst zadatka i ja vam taj prevod dostavljam u originalu sada, mozda sam ja nesto pogresno shvatio pa mi vi mozete pomoci da ne radim suvisne operacije ako nisu potrebne :)

Citat:

Prosirite dati program za sortiranje sort.c sa predavanja tako da s njim mozete uporedjivati slozenost i ponasanje algoritama za sortiranje Bubble-Sort Insertion-Sort, Selection-Sort i Merge-Sort za razlicite Array-velicine i Array-tipove
Pri tom prilagodite u data 4 algoritma za sortiranje varijable za mjerenje broja operacija poredjenja i zamjene. Zatim izvedite algoritme za sortiranje za svaki od tri ista niza (Arrays) velicine n, jedan nasumicno izabran , jedan sortiran u rastucem poredku i jedan u opadajucem
Protokoliraj uz to broj operacija poredjenje i zamjene I dajte rezultat u vidu tabele
Velicina niza (array) treba biti data kao parameter komandne linije (Kommandozeilenparametar). Analizirajte tabelarni izdanje za nizove velicine 10, 100 i 10000 I interpretirajte rezultat

Prikačeni fajlovi

sort.c - 7.63k

Odgovor na temu

ksrele
Programer - informatičar
Gold Drink D.O.O. Subotica
Subotica

Član broj: 14253
Poruke: 1642
*.dynamic.isp.telekom.rs.

ICQ: 66444502

+47 Profil

Re: Poredjenje sortiranja

^{12.12.2010. u 21:20 - pre 162 meseci}

P.S.
E da, zaboravio sam da kazem da na ovom Merge Sort algoritmu nisam ubacio rikverc sortiranje jer veze nemam kao to da uradim, previse je zakomplikovano...

Tako da ako mozete pomozite...

Odgovor na temu

ksrele
Programer - informatičar
Gold Drink D.O.O. Subotica
Subotica

Član broj: 14253
Poruke: 1642
*.dynamic.isp.telekom.rs.

ICQ: 66444502

+47 Profil

Re: Poredjenje sortiranja

^{12.12.2010. u 22:30 - pre 162 meseci}

Hmmm... sada nesto kontam, pa nije ni potrebno da svi algoritmi mogu da sortiraju u rikverc, vec trebaju da sortiraju nizove koji su sortirani u rikverc... e bedaka... ja se tu mucio da ih napravim da rade u rikverc a nije ni potrebno... :)
Mada, ako je potrebno da se sortira niz koji je sortiran u rikverc onda ga ja moram nekako generisati, a to cu uraditi upravo tako sto ce jedan od algoritama moci da sortira u opadajucem rasporedu.
Ali, ako ipak neko ima ideju kako ovaj Merge Sort da prepravim da radi u suprotnom smeru bilo bi cool.

Odgovor na temu

ksrele
Programer - informatičar
Gold Drink D.O.O. Subotica
Subotica

Član broj: 14253
Poruke: 1642
*.dynamic.isp.telekom.rs.

ICQ: 66444502

+47 Profil

Re: Poredjenje sortiranja

^{14.12.2010. u 00:10 - pre 162 meseci}

Ne mogu da verujem da mi niko ne moze pomoci iako sam vam pokazao da znam da uradim nesto i da nisam totalni pocetnik...
Ufff... mozda trazim pomoc na pogresnom mestu.
U svakom slucaju, evo koda sto sam uradio. Mozda je tacno ali verovatno da nije.
Uz poruku prilazem i .exe file (prilozio bi i za Linux kompajlirano ali ne znam kako da kompajliram za Linux iz Windowsa) jer znam da NIKO nece hteti pogledati source kod.
Probajte ga sa nekim velicinama niza i kazite mi da li rezultati imaju smisla?
Posto cisto sumnjam da ce i to neko da sam pokrene exe file, ja prilazem i rezultate mog testiranja za velicinu niza od 10000 clanova.

Code:

Generating arrays...
+=======================================================================+
|Input array|Data type  |Sort method|No. compar.|No. swaps  |Elap. time |
|-----------|-----------|-----------|-----------|-----------|-----------|
|Unsorted   |Integer    |Bubble     |99060093   |25052808   |360ms      |
|-----------+-----------+-----------+-----------+-----------+-----------|
|Unsorted   |Float      |Bubble     |197790219  |24893845   |562ms      |
|-----------+-----------+-----------+-----------+-----------+-----------|
|Unsorted   |Double     |Bubble     |297240273  |25144059   |609ms      |
|-----------+-----------+-----------+-----------+-----------+-----------|
|Unsorted   |Integer    |Insertion  |9999       |7762       |0ms        |
|-----------+-----------+-----------+-----------+-----------+-----------|
|Unsorted   |Float      |Insertion  |19998      |5134       |0ms        |
|-----------+-----------+-----------+-----------+-----------+-----------|
|Unsorted   |Double     |Insertion  |29997      |0          |0ms        |
|-----------+-----------+-----------+-----------+-----------+-----------|
|Unsorted   |Integer    |Selection  |49995000   |9999       |110ms      |
|-----------+-----------+-----------+-----------+-----------+-----------|
|Unsorted   |Float      |Selection  |99990000   |9999       |172ms      |
|-----------+-----------+-----------+-----------+-----------+-----------|
|Unsorted   |Double     |Selection  |149985000  |9999       |187ms      |
|-----------+-----------+-----------+-----------+-----------+-----------|
|Unsorted   |Integer    |Merge      |76755      |7761       |0ms        |
|-----------+-----------+-----------+-----------+-----------+-----------|
|Unsorted   |Float      |Merge      |150882     |5133       |0ms        |
|-----------+-----------+-----------+-----------+-----------+-----------|
|Unsorted   |Double     |Merge      |219890     |5000       |16ms       |
|-----------+-----------+-----------+-----------+-----------+-----------|
|ASC        |Integer    |Bubble     |297250272  |0          |0ms        |
|-----------+-----------+-----------+-----------+-----------+-----------|
|ASC        |Float      |Bubble     |297260271  |0          |0ms        |
|-----------+-----------+-----------+-----------+-----------+-----------|
|ASC        |Double     |Bubble     |297270270  |0          |0ms        |
|-----------+-----------+-----------+-----------+-----------+-----------|
|ASC        |Integer    |Insertion  |39996      |7759       |0ms        |
|-----------+-----------+-----------+-----------+-----------+-----------|
|ASC        |Float      |Insertion  |49995      |5131       |0ms        |
|-----------+-----------+-----------+-----------+-----------+-----------|
|ASC        |Double     |Insertion  |59994      |0          |0ms        |
|-----------+-----------+-----------+-----------+-----------+-----------|
|ASC        |Integer    |Selection  |199980000  |9999       |109ms      |
|-----------+-----------+-----------+-----------+-----------+-----------|
|ASC        |Float      |Selection  |249975000  |9999       |172ms      |
|-----------+-----------+-----------+-----------+-----------+-----------|
|ASC        |Double     |Selection  |299970000  |9999       |172ms      |
|-----------+-----------+-----------+-----------+-----------+-----------|
|ASC        |Integer    |Merge      |296642     |7758       |0ms        |
|-----------+-----------+-----------+-----------+-----------+-----------|
|ASC        |Float      |Merge      |370766     |5130       |0ms        |
|-----------+-----------+-----------+-----------+-----------+-----------|
|ASC        |Double     |Merge      |439774     |5000       |0ms        |
|-----------+-----------+-----------+-----------+-----------+-----------|
|DESC       |Integer    |Bubble     |397240272  |49944986   |266ms      |
|-----------+-----------+-----------+-----------+-----------+-----------|
|DESC       |Float      |Bubble     |497230272  |49993407   |406ms      |
|-----------+-----------+-----------+-----------+-----------+-----------|
|DESC       |Double     |Bubble     |597220272  |49993429   |500ms      |
|-----------+-----------+-----------+-----------+-----------+-----------|
|DESC       |Integer    |Insertion  |99990      |7756       |0ms        |
|-----------+-----------+-----------+-----------+-----------+-----------|
|DESC       |Float      |Insertion  |109989     |5128       |0ms        |
|-----------+-----------+-----------+-----------+-----------+-----------|
|DESC       |Double     |Insertion  |119988     |0          |0ms        |
|-----------+-----------+-----------+-----------+-----------+-----------|
|DESC       |Integer    |Selection  |349965000  |9999       |94ms       |
|-----------+-----------+-----------+-----------+-----------+-----------|
|DESC       |Float      |Selection  |399960000  |9999       |187ms      |
|-----------+-----------+-----------+-----------+-----------+-----------|
|DESC       |Double     |Selection  |449955000  |9999       |172ms      |
|-----------+-----------+-----------+-----------+-----------+-----------|
|DESC       |Integer    |Merge      |516523     |7755       |16ms       |
|-----------+-----------+-----------+-----------+-----------+-----------|
|DESC       |Float      |Merge      |590644     |5127       |0ms        |
|-----------+-----------+-----------+-----------+-----------+-----------|
|DESC       |Double     |Merge      |659652     |5000       |0ms        |
+=======================================================================+
All sorting finished successfully!

Prikačeni fajlovi

sort.c - 26.13k

sort.exe - 44.32k

Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249

+96 Profil

Re: Poredjenje sortiranja

^{14.12.2010. u 09:23 - pre 162 meseci}

Ne znam kako je drugima, ali ja pomažem tako što neko stavi kod i kaže imam grešku u kodu. Onda ja pogledam kod i nađem grešku. Svi ostali scenariji mi nisu od interesa.

Odgovor na temu

ksrele
Programer - informatičar
Gold Drink D.O.O. Subotica
Subotica

Član broj: 14253
Poruke: 1642
*.dynamic.isp.telekom.rs.

ICQ: 66444502

+47 Profil

Re: Poredjenje sortiranja

^{14.12.2010. u 14:03 - pre 162 meseci}

A sta ako ja ne znam da ima greska u kodu?
Program radi bez problema to sto sam ja isprogramirao, e sad, jedino se pitam da li sam ja dobro isprogramirao to sto treba da radi...
Ma samo mi pogledajte da li sam na prava mesta stavio brojace poredjenja i brojace promene clanova niza. Verovatno se neko od vas bavio sa ovim problemom sortiranja ranije...
Pa nista, ako mi niko ne pomognem dajem prijateljici ovako uradjen zadatak pa ce mene biti sramota kada joj jave da nije dobar.
Uzgred, njen fax nema mnogo veze sa programiranjem, mislim da je neka biologija ili vec neka prirodna nauka u pitanju tako da joj C bas i nije jasan kao programski jezik.

Odgovor na temu

Mihajlo Cvetanović
Beograd

Moderator
Član broj: 37636
Poruke: 1249

+96 Profil

Re: Poredjenje sortiranja

^{14.12.2010. u 14:29 - pre 162 meseci}

Ovako na prvi pogled u merge sortu ne brojiš swapove nego dodele. Pretpostavljam da swapova po definiciji ima tačno duplo manje od dodela, ali tek kad se uračuna i inicijalizacija tmp niza.

U insertion sortu poređenje je u while petljama, ali brojač poređenja je izvan petlje. Bolje stavi da petlja gleda samo na j >= 0, a drugu proveru stavi unutra sa break, i onda i brojač stavi pre same provere, ali u petlji. Ostalo bi trebalo da je dobro.

Uzgred, moguće je da ovaj domaći i nije za tvoju koleginicu (lepo kažeš, šta će pa C biolozima) nego za neku drugu, ili nekog drugog...

Odgovor na temu

ksrele
Programer - informatičar
Gold Drink D.O.O. Subotica
Subotica

Član broj: 14253
Poruke: 1642
*.dynamic.isp.telekom.rs.

ICQ: 66444502

+47 Profil

Re: Poredjenje sortiranja

^{14.12.2010. u 17:24 - pre 162 meseci}

Prvo, hvala na pomoci.
Drugo, moze li malo detaljnije?

Citat:

Mihajlo Cvetanović: Ovako na prvi pogled u merge sortu ne brojiš swapove nego dodele. Pretpostavljam da swapova po definiciji ima tačno duplo manje od dodela, ali tek kad se uračuna i inicijalizacija tmp niza.

Wikipedia kaze:

Citat:

In the worst case, merge sort does an amount of comparisons equal to or slightly smaller than (n ⌈lg n⌉ - 2⌈lg n⌉ + 1), which is between (n lg n - n + 1) and (n lg n + n + O(lg n)).

Iskreno, zaista nemam pojma gde da postavim brojanje da se sve tacno izbroji.
Programiranje algoritama za sortiranje sam radio nekad (relativno davno) i obicno sam radio one jednostavne (bubble i quick) sa ovim komplikovanijim se prvi put srecem, ali nikad nisam razmisljao o tome kako da prebrojim broj koraka.
Mislis da bi trebao broj swapova da povecam za broj clanova niza? Jer bi se tada u broj swapova ubrojala i definicija TEMP niza? Doduse, to se sve radi rekurzivno... Ufff.. glava me zabole, zaista nemam pojma gde i kako da ubacim ove brojace u ovaj Merge sort...

Citat:

Mihajlo Cvetanović: U insertion sortu poređenje je u while petljama, ali brojač poređenja je izvan petlje. Bolje stavi da petlja gleda samo na j >= 0, a drugu proveru stavi unutra sa break, i onda i brojač stavi pre same provere, ali u petlji.

Mislio si na ovo: (nisam jos probao da kompajliram i probam ovako, ovo je samo na brzaka pitanje)

Code (c):

for (i = 1; i < length; i++) {

     key = arr[i];

     j = i - 1;

     ins_comp_count++; //-ovu da iskljucim ili sta?

     while (j >= 0) {

             if(key < arr[j])

             {

                ins_comp_count++;  //-ovde sam stavio dodatno brojanje, ovako treba?

                break;

             } 

          ins_swap_count++;

          arr[j + 1] = arr[j];

          j--;

     }

     arr[j + 1] = key;

}

Citat:

Mihajlo Cvetanović: Uzgred, moguće je da ovaj domaći i nije za tvoju koleginicu (lepo kažeš, šta će pa C biolozima) nego za neku drugu, ili nekog drugog...

Pa ako me komsija laze i kaze da mu cerka u Nemackoj ne zna da resi ovaj zadatak i zamolio me da joj pomognem onda i ja lazem vas... Ionako verovatno radim za dzabe tako da...
Sve u svemu ISKRENO kazem: nije za mene licno, ja radim u PHP-u i VB-u a ne u C-u.

Hvala na pomoci, moze li jos koja?

Odgovor na temu