Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
Listide sorteermine > module ListSort where > import ListComb (perms) Listi sorteerimine on sellise listi permutatsiooni leidmine, kus kõik listi elemendid on järjestatud. Pannes selle spetsifikatsiooni otse Haskelli, saame: > verySlowSort xs = head [ys | ys <- perms xs, sorted ys] > where sorted xs = and [ x <= y | (x,y) <- zip xs (tail xs)] On selge, et toodud definitsioon on ülimalt ebaefektiivne, kuna potensiaalselt genereeritakse kõik listi permutatsioonid (mida on n! tükki). 1. 'Selection sort' Naiivseim "reaalne" sorteerimisalgoritm töötab järgmiselt: leiame listist vähima elemendi ja paneme ta tulemlisti esimeseks. Seejärel leiame järele jäänud listist jällegi vähima ja paneme ta tulemlisti teiseks. Toimime analoogiliselt kuni kogu list on sorteeritud. Antud algoritm on tuntud nime 'selection sort' all ning tema võimalik realisatsioon Haskellis on järgmine: > ssort [] = [] > ssort xs = y : ssort ys > where y = minimum xs > (ys1,ys2) = break (==y) xs > ys = ys1 ++ (tail ys2) Siin, 'minimum' ja 'break' on standardfunktsioonid; esimene leiab listi vähima elemendi, teine lõikab listi kaheks sellest kohast, kus predikaat on täidetud. Nende fuktsioonide võimalikud definitsioonid on näiteks järgmised: minimum [x] = x minimum (x:xs) = x `min` minimum xs break p xs = takeWhile (not . p) xs ++ dropWhile (not . p) xs Kuna listi sorteerimise igal sammul leitakse listist vähim element (mille leidmiseks peab kogu listi läbi vaatama), siis on selge, et toodud sorteerimisalgoritm on alati ruutkeerukusega. 2. 'Insertion sort' Järgmine lihtne sorteerimisalgoritm töötab järgmiselt: sorteerime ära listi saba ja seejärel lisame esialgse listi pea juba sorteeritud list nii, et tulemusena saadav list oleks sorteeritud. Toodud algoritmi tuntakse nime 'insertion sort' all. Haskellis võiks see välja näha järgmiselt: > isort [] = [] > isort (x:xs) = insert x (isort xs) > where insert x [] = [x] > insert x (y:ys) | x <= y = x : y : ys > | otherwise = y : insert x ys Kuna listi sorteerimise igal sammul lisatakse juba sorteeritud listi uus element, siis on selge, et toodud sorteerimisalgoritm on halvimal juhul ruutkeerukusega. Kui aga list on juba algselt sorteeritud, siis on uue elemendi lisamine tehtav ühe sammuga ja seega on sellisel juhul 'insertion sort' lineaarse keerukusega. Teatud mõttes on 'selection sort' ja 'insertion sort' teineteisega duaalsed. Mõlema algoritmi korral võetakse igal sammul üks element, mis seejärel lisatakse juba sorteeritud listi. 'Selection sorti' korral on elemendi valimine suhteliselt töömahukas operatsioon (vähima elemendi leidmine) ning elemendi lisamine triviaalne operatsioon (elemendi panemine listi peaks). 'Insertion sorti' korral on asi täpselt vastupidi; elemendi valik on triviaalne (võetakse listi pea) ning elemendi lisamine on suhteliselt töömahukas. Kumbagi algoritmi saab efektiivsemaks teha kasutades nn. jaga ja valitse (divide and conquer) tehnikat. Idee seisneb selles, et me jagame sisendlisti kaheks enamvähem võrdse pikkusega listiks. Seejärel mõlemad alamlistid sorteeritakse ning saadavad sorteeritud listid kombineeritakse kokku lõpptulemuseks. Sõltuvalt sellest kumb operatsioonidest -- kas listide pooleks jagamine või kokku panemine -- on keeruline ja kumb lihtne, saame vastavalt algoritmid mida tuntakse nimede all 'quick sort' ja 'merge sort'. 3. 'Quick sort' 'Quick sordi' korral võetakse listist "juhuslikult" üks element ning jagatakse list kaheks -- esimeses on antud elemendist kõik väiksemad elemendid, teises kõik suuremad (ja võrdsed) elemendid. Pärast alamlistide sorteerimist konkateneeritakse mõlemad listid kokku lõpptulemuseks. Toodud kirjelduse võimalik realisatsioon Haskellis on järgmine: > qsort [] = [] > qsort (x:xs) = qsort [u | u <- xs, u < x ] ++ > [x] ++ > qsort [u | u <- xs, u >= x] Paneme tähele, et selleks "juhuslikuks" elemendiks võtame me alati listi pea. Põhjus peitub loomulikult selles, et listi pea võtmine on kõige lihtsam (ja efektiivsem) moodus elemendi valikuks. Oletates, et listi elemendid on tõepoolest juhusliku jaotusega, on kumbki alamlist enamvähem ühepikkusega. Seega on 'quick sort' tavaliselt keerukusega (n * log2 n). Kui aga list on juba algul järjestatud, siis on esimene list tühi ning kõik elemendid asetsevad teises listis. Selle tulemusena on järjestatud listi "sorteerimine" 'quick sordi' abil ruutkeerukusega. (Sisuliselt langeb 'quick sort' sellel juhul kokku 'selection sordiga'). 4. 'Merge sort' Duaalsena 'quick sordile' on 'merge sordi' korral listi kaheks jagamine lihtne -- list lüüakse pooleks täpselt keskkohast. Kogu sisuline töö tehakse kahe sorteeritud listi 'kokkusulatamisel' üheks. > msort xs | n <= 1 = xs > | otherwise = merge (msort us) (msort vs) > where n = length xs > us = take (n `div` 2) xs > vs = drop (n `div` 2) xs > merge [] ys = ys > merge xs [] = xs > merge (x:xs) (y:ys) | x < y = x : merge xs (y:ys) > | otherwise = y : merge (x:xs) ys Kuna alamlistid on alati praktiliselt ühepikkusega (täpsemalt, nad on kas ühepikad või on teises üks element esimesest rohkem), siis on toodud algoritmi keerukus alati (n * log2 n). KOKKUVÕTE |------------------------------------------------------| | kaheks löömine | keeruline | lihtne | | kokku panemine | lihtne | keeruline | |------------------------------------------------------| | üks alamülesanne | selection sort | insertion sort | | - parim keerukus | n^2 | n | | - halvim keerukus | n^2 | n^2 | |------------------------------------------------------| | kaks alamülesannet | quick sort | merge sort | | - parim keerukus | n * log2 n | n * log2 n | | - halvim keerukus | n^2 | n * log2 n | |------------------------------------------------------|