Sortirni algoritmi - kako delujejo

Vse o programiranju na in za PC

Moderatorji: Kroko, tilz0R

Sortirni algoritmi - kako delujejo

OdgovorNapisal/-a sundancer » 27 Sep 2019, 16:40

Z zvokom opremljena vizualizacija sortirnih algoritmov.
Prikazuje kako delujejo sortirni algoritmi nad množico celih števil. Večini algoritmov je skupno to, da opravilo sortiranja razbijejo na več manjših opravil; torej sortirajo po manjših kosih. Sicer pa si oglejte posnetek, ki je zelo zgovoren.

https://www.youtube.com/watch?v=kPRA0W1kECg



Eden izmed algoritmov na posnetku ima soimenjaka na našem forumu :)
Uporabniški avatar
sundancer
 
Prispevkov: 537
Pridružen: 16 Jan 2015, 22:36
Kraj: Domžale
Zahvalil se je: 184 krat
Prejel zahvalo: 275 krat
Uporabnika povabil: Vrtni palček
Število neizkoriščenih povabil: 38

Re: Sortirni algoritmi - kako delujejo

OdgovorNapisal/-a VolkD » 27 Sep 2019, 18:03

Vsem tem algoritmom je skupna ena stvar. Čas sortiranja je močno odvisen od tega koliko je že od prej zadeva delno sortirana.
Nekateri so celo taki, ki imajo najdaljši čas, če jim damo v sortiranje že sortiran niz elementov.
Dokler bodo ljudje mislili, da živali ne čutijo bolečine, bodo živali čutile, da ljudje ne mislijowww.S5tech.net
Uporabniški avatar
VolkD
Administratorji strani
 
Prispevkov: 37390
Pridružen: 29 Dec 2014, 19:49
Kraj: Kačiče (Divača)
Zahvalil se je: 7539 krat
Prejel zahvalo: 4565 krat
Uporabnika povabil: Vrtni palček
Število neizkoriščenih povabil: 255

Re: Sortirni algoritmi - kako delujejo

OdgovorNapisal/-a VolkD » 27 Sep 2019, 18:17

Tudi sam sem avtor enega od algoritmov za sortiranje. Pravzaprav nisem nič novega izumil, le sestavil sem skupaj stvari, ki so že znane.
Različni algoritmi imajo različne časovne odzive glede na število elementov niza, ki jih je potrebno sortirati. Pri katerem oziroma okrog katerega števila elementov je kateri algoritem najboljši je odvisno od marsičesa.
Moj sort je tak, da vsebuje sedem znanih algoritmov in za vseh sedem na nekem računalniku poišče idealne časovne odzive glede na število elementov, odzive si zapolni in služijo za kasnejša sortiranja. Naredi torej nekakšno konfiguracijsko datoteko.
Od teh sedmih so štirje algoritmi taki, ki imajo v posameznih fazah problem razdeljen na več manjših delov, vsak del pa glede na ostale vsebuje le elemete, ki ustrezajo temu delu. V tem trenutku se sortiranje ustavi, pregleda se dolžine teh segmentov in se jih ponudi v sortiranje algoritmu, ki je pri tej dolžini najhitrejši.

Algoritem sem uporabljal v svojih poslovnih aplikacijah (nastal je pred več kot 40-imi leti). V teh aplikacijah se je mnogokrat zgodilo, da so bili podatki že delno sortirani. V takem primeru je nastopil problem, da je cel niz razpadel na en del dolžine treh elementov in drug del v katerem so bili preostali podatki. To pa je bila najbolj neugodna možna varianta kar se časovnega odziva tiče.

Celi zadevi sem dodal "predsort", ki je elemente najprej razmetal čim bolj naključno. Hitrost celotnega tako narejenega programa za sortiranje je bila v končni fazi še najbolj odvisna od naključnega generatorja, ki je elemete premetal na samem začetku.

Algoritem je nastal še na IBM-jevem računalniku S3 in je bil napisan v RPGII jeziku. Takrat še ni imel konfiguracijske datoteke, ampak so bile v program vpisane kar konstante, pridobljene z izkušnjami.
Dokler bodo ljudje mislili, da živali ne čutijo bolečine, bodo živali čutile, da ljudje ne mislijowww.S5tech.net
Uporabniški avatar
VolkD
Administratorji strani
 
Prispevkov: 37390
Pridružen: 29 Dec 2014, 19:49
Kraj: Kačiče (Divača)
Zahvalil se je: 7539 krat
Prejel zahvalo: 4565 krat
Uporabnika povabil: Vrtni palček
Število neizkoriščenih povabil: 255

Re: Sortirni algoritmi - kako delujejo

OdgovorNapisal/-a VolkD » 27 Sep 2019, 18:25

VolkD je napisal/-a: V teh aplikacijah se je mnogokrat zgodilo, da so bili podatki že delno sortirani. V takem primeru je nastopil problem, da je cel niz razpadel na en del dolžine treh elementov in drug del v katerem so bili preostali podatki. To pa je bila najbolj neugodna možna varianta kar se časovnega odziva tiče.

Ne samo časovno, tudi drugače je bila ta situacija zelo neugodna. S3 je takrat imel 16k spomina. Ja 16k, prav ste prebrali. Algoritem je bil seveda rekurziven. V primeru že sortiranega niza se je lahko, če je bilo podatkov mnogo, zgodilo, da je zmanjkalo prostora za stack.
Dokler bodo ljudje mislili, da živali ne čutijo bolečine, bodo živali čutile, da ljudje ne mislijowww.S5tech.net
Uporabniški avatar
VolkD
Administratorji strani
 
Prispevkov: 37390
Pridružen: 29 Dec 2014, 19:49
Kraj: Kačiče (Divača)
Zahvalil se je: 7539 krat
Prejel zahvalo: 4565 krat
Uporabnika povabil: Vrtni palček
Število neizkoriščenih povabil: 255

Re: Sortirni algoritmi - kako delujejo

OdgovorNapisal/-a VolkD » 27 Sep 2019, 18:34

S3 je sicer imel znotraj svojega OS program za sortiranje podatkov, a je bil milo rečeno zanič. Pri številu elementov pod 45 je bil hitrejši od mojega sorta. Tam nekje do 200 sta si bila dokaj enakovredna. Pri številu elementov nad 2500 je bil moj algoritem za faktor 10x in več hitrejši.

Takrat sem delal v Javor Pivka in nismo imeli svojega računalnika. Gostovali smo v Alpina v Žireh, kasneje pa v Stol Kamnik. Vsako uro računalnika je bilo seveda treba plačati. Obdelave podatkov so se največkrat izvajale tako, da se je podatke sortiralo in potem tako urejene izpisovalo, pri tem so se tvorili vmesni seštevki in rekapitulacije na koncu. Kar precej sortiranja torej.
Svoji firmi sem torej prihranil kar precej denarja. No takrat se tega sploh nisem zavedal, niti mi ni bilo pomembno. Rešil sem namreč en drug čisto moj problem.
Ker smo gostovali in računalnik ni bil poceni stroj, smo termine na njem dobili, ko ga lastniki niso potrebovali; torej pozno popoldan in ponoči.
S tem algoritmom sem torej hodil domov ob 2 ali 3 namesto zjutraj.
Dokler bodo ljudje mislili, da živali ne čutijo bolečine, bodo živali čutile, da ljudje ne mislijowww.S5tech.net
Uporabniški avatar
VolkD
Administratorji strani
 
Prispevkov: 37390
Pridružen: 29 Dec 2014, 19:49
Kraj: Kačiče (Divača)
Zahvalil se je: 7539 krat
Prejel zahvalo: 4565 krat
Uporabnika povabil: Vrtni palček
Število neizkoriščenih povabil: 255

Re: Sortirni algoritmi - kako delujejo

OdgovorNapisal/-a peterp » 27 Sep 2019, 18:57

Koliko vrstic pa je imel cel program? In lahko napišeš malo bolj podrobno kaj je počel?
peterp
 
Prispevkov: 610
Pridružen: 23 Feb 2015, 13:52
Kraj: Maribor
Zahvalil se je: 144 krat
Prejel zahvalo: 93 krat
Uporabnika povabil: gumby
Število neizkoriščenih povabil: 95

Re: Sortirni algoritmi - kako delujejo

OdgovorNapisal/-a VolkD » 27 Sep 2019, 20:46

Težko bi zdaj o vrsticah, ker se je cela zadeva razvijala skozi leta.
No če bi začel povsem na začetku, bi raje kot o vrsticah govoril o karticah. Težko bom zdajle rekel o številu, ampak v spominu imam šop kartic debeline nekje okrog 12 cm. Govorimo seveda o jeziku RPG II. Takrat je celoten program imel vključene le tri algoritme. In le eden je bil tak, da je celotem problem razpadel na več delov. Druga dva sta bila bubble sort in vsak z vsakim.

Kasneje sem to prestavil v Pascal. Spočetka je bil to Turbo pascal 3.0 za CPM sisteme in seveda Iskrin Partner. Tu je bilo vse drugače. Bistveno bolj sposoben CPU in nekaj hitrejši disk Segate 10MB (10MB je prav, ni GB ali celo TB). Odpadel je algoritem vsak z vsakim, ker se je izkazalo, da je skoraj neuporaben. Namesto njega sem vgradil quick sort, ki je bil takrat zelo popularen. Pohitritev je bila več kot očitna. No na Partnerju sem delal le eno leto, potem so prišli PC XT-ji.

Takrat sem delal v računskem centru Zdravstvenega centra v Kopru. Osnoven računalnik je bil IBM4331. Škatla, ki je v Nemčiji odslužila svoje, pri nas pa je bila hudo moderna zadeva. Žal stvar ni imela pascal prevajalnika, prepisovanje v PLI ali pa celo v meni osovražen Cobol pa se mi ni dalo.
Nekako se je slutilo, da bodo mainframe mašine postale neaktualne, zato sem se tega potem lotil na XT-ju. Takrat smo imeli enega samega. Najprej je bil tri mesece pri šefici, ko je ugotovila, da z njim nima kaj početi, sem ga bil deležen jaz.
V tistih časih je bil radio študent nakakšno zbirališče programerjev. Verjetno je temu botrovalo oddajanje v eter in sicer programov za ZX Spectrum. Iz tega okolja sem privlekel piratsko kopijo Turbo pascala 3.0 in 4.0.

Verzija 4.0 je bila mala katastrofa. Oh ne, nič narobe ni bilo z njo. Problem je bil, da je bila malček pred časom, oziroma precej pred nami. Takrat se je že dobilo 386 računalnike in tudi take, ki so imeli posebej še koprocesor. Mi smo bili pa še vedno na XT, torej 86 mlinčku. Dejstvo se je reflektiralo v tem, da je bil pritisk "bolj hitro" precej večji, kot bi sicer bil.
Algoritem je dobil še dva sorta, mislim, da merge in insertion sort.
Takrat sem tudi videl, da je moj sistem razdeljevanja problema na manjše dele milorečeno slab. To sem odkril zato, ker sem ugotovil, da se mi en element zgubi, če ima vhodni niz (2 na n)+1 elementov, pod pogojem, da je n neparen in večji od 5. Da bo stvar še malo slabša se namesto tega elementa v zbirki pojavi eden od drugih elementov kot dvojen. To je napaka, ki jo je izjemno težko odkriti. Po kakih 14-ih dneh sem obupal in raje implementiral že preizkušen bucket algoritem.
Nimam pojma koliko vrstic je takrat vsebovala koda.
Jaz sem bil zadovoljen, saj se je čas sortiranja močno približal času branja in zapisovanja na disk.

Za dolgo časa sem opustil delo na tem področju, preprosto nisem verjel, da bi čas sortiranja lahko prepolovil. In tudi če bi mi to uspelo, bi se celoten rezultat odrazi kvečjemu kot 25% prihranek časa, saj bi ostalo branje in pisanje enako hitro.

Takrat je program bil en sam monoliten blok s procedurami. TP3.0 še ni poznal knjižnic (UNIT je prišel kasneje)
Dokler bodo ljudje mislili, da živali ne čutijo bolečine, bodo živali čutile, da ljudje ne mislijowww.S5tech.net
Uporabniški avatar
VolkD
Administratorji strani
 
Prispevkov: 37390
Pridružen: 29 Dec 2014, 19:49
Kraj: Kačiče (Divača)
Zahvalil se je: 7539 krat
Prejel zahvalo: 4565 krat
Uporabnika povabil: Vrtni palček
Število neizkoriščenih povabil: 255


Vrni se na Programski jeziki

Kdo je na strani

Po forumu brska: 0 registriranih uporabnikov in 1 gost