[LUGOS-PROG] Mergesort iterativno

[Uroš Golja]

Nisem šel preverjat, ali tvoj algoritem deluje pravilno ali ne... to 
ugotovi sam.

Kolikor vidim takole čez palec, je edina razlika v tem, da si 'uradni' 
quicksort pred izvajanjem premen načrtno izbere srednji element 
(median), ki mu loči levi in desni del neurejenega zaporedja. Ti 
privzameš, da je srednji element kar na sredini neurejenega zaporedja, 
kar ni vedno res... tvoja možnost, da zadeneš srednji element, je le 1/n.

Srednji element je po definiciji tisti element, ki v končnem (=urejenem) 
zaporedju zaseda srednje mesto (n div 2).

Izbira srednjega elementa pred izvajanjem premen izboljšuje učinkovitost 
algoritma, ker se v tem primeru neurejeno zaporedje vedno prelomi na po 
dolžini dva (skoraj) enaka dela.

Izboljšava izhaja iz kontraprimera: quicksort se najslabše obnaša 
takrat, kadar neurejeno zaporedje dolžine n razpade na dva dela, od 
katerih je en 'velik' n-1 element, drugi pa 'majhen' 1 element.

Aja, še mojih pet centov: pri tvojem primeru (<10 elementov v zaporedju) 
je popolnoma vseeno, kateri algoritem za sortiranje uporabiš. Grem 
stavit za pir, da ti navadno izbiranje hitreje uredi deset elementov kot 
pa quicksort.

LP,
Uroš



Simon Striker wrote:

>Hello Uroš,
>
>Wednesday, November 5, 2003, 3:15:34 PM, you wrote:
>
>Uroš> Umm...
>
>Uroš> tale tvoj algoritem sploh ni mergesort (=zlivanje), ampak quicksort
>Uroš> (=sortiranje s premenami). Mergesort se uporablja pri zunanjem 
>Uroš> sortiranju (=sortiranje datotek oziroma trakov), quicksort pa za
>Uroš> notranje sortiranje (=sortiranje v pomnilniku). Ker očitno sortiraš v
>Uroš> pomnilniku, rabiš algoritem za notranje sortiranje.
>
>Uroš> Rekurzivne izvedbe mergesorta še nisem videl nikjer, pa tudi smiselna
>Uroš> ni. Iterativnih izvedb quicksorta pa mora biti na webu vse polno. Google
>Uroš> is your friend. Išči quicksort in iterative.
>
>In kakšna je potem razlika med mojim algoritmom (kateremu ti praviš
>quicksort) in quicksort algoritmom, kot ga najdeš na spodnjem naslovu:
>
>http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quicken.htm
>
>in še opis mergesorta:
>
>http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/merge/mergen.htm
>
>LP, Simon
>-------------
>Best regards,
>
>Simon Striker
>Rusjanov trg 2
>1000 Ljubljana   +38641473856
>
>E-mail: simon.striker at telemach.net
>
>
>  
>