Hidas lajittelu
Slowsort on epäkäytännöllinen ja humoristinen lajittelualgoritmi . Se perustuu periaatteeseen moninkertaista ja antaudu (eng. multiply and surrender ), joka on parodia jakaa ja hallitse . Sen julkaisivat Andrey Broder ja Jorge Stolfi vuonna 1986 artikkelissaan Pessimal Algorithms and Simplexity Analysis [1] ( Pessimal Algorithms and Simplicity Analysis , parodia optimaalisista algoritmeista ja kompleksisuusanalyysistä ).
Algoritmi
Hidas lajittelu on rekursiivinen algoritmi . Pseudokoodissa se toteutetaan seuraavasti:
Aliohjelma slowsort(A,i,j) // lajittelee taulukon A[i], ..., A[j] jos i >= j sitten palauttaa m := ⌊(i+j)/2⌋ hidas lajittelu(A,i,m) // (1.1) hidas lajittelu(A,m+1,j) // (1.2) jos A[j] < A[m] , vaihda A[j] ja A[m] // (1.3) hidas lajittelu(A,i,j-1) // (2)- Lajittele rekursiivisesti ensimmäinen puolisko (1.1);
- Lajittele rekursiivisesti toinen puolisko (1.2);
- Etsi koko taulukon maksimi vertaamalla 1.1 ja 1.2 tuloksia ja laita se taulukon (1.3) loppuun;
- Lajittele rekursiivisesti koko taulukko enimmäismäärää lukuun ottamatta.
Mahdollinen toteutus Haskellissa :
hidas lajittelu :: Järjestys a => [a] -> [a] hidas lajittelu xs | pituus xs <= 1 = xs | muuten = hidas lajittelu xsnew ++ [max last rlast] -- (2) missä l = hidas lajittelu $ ota m xs -- (1.1) r = hidas lajittelu $ pudota m xs -- (1.2) viimeinen = viimeinen l rlast = viimeinen r xsnew = init l ++ min llast rlast : init r m = fst(divMod(pituus xs) 2)Vaikeus
Hitaan lajittelun suoritusaika on . Hidas lajittelu ei ole polynomiajassa . Parhaimmillaankin se on huonompi kuin kuplatyyppi .
Lähteet
- ↑ CiteSeerX - Pessimaaliset algoritmit ja yksinkertaisuusanalyysi . Citeseerx.ist.psu.edu . Haettu 26. heinäkuuta 2017. Arkistoitu alkuperäisestä 30. tammikuuta 2017.
| Lajittelualgoritmit | |
|---|---|
| Teoria | Monimutkaisuus O merkintä Tilaussuhde Lajittele tyypit kestävää Sisäinen Ulkoinen |
| Vaihto | |
| Valinta | |
| insertit | |
| fuusio | |
| Ei vertailuja | |
| hybridi | |
| Muut | |
| epäkäytännöllistä | |