Üksuste sortimine loendis on igapäevane ülesanne ja sageli aeganõudev. Mõiste sortimine tähendab üldjuhul üksuste loendisse paigutamist kas kasvavas või kahanevas järjekorras, tuginedes eelnevalt kindlaksmääratud tellimussuhtele. Sorteerimine on sageli ette nähtud otsimiseks, mis on tema järjekordne põhiline tegevus andmetöötluses. Kujutage ette, kui keeruline oleks olnud sõnaraamatust sõna otsida, kui selles sisalduvaid sõnu poleks korraldatud ega järjestatud. See on põhjus, miks sõnastiku kirjeid peetakse tavapärases tähestiku järjekorras. Arvukad ülesanded ja arvutused muutuvad vaevata lihtsalt sorteerimise teel. Ja just siin tulevad pildile sortimisalgoritmid.

Sorteerimise algoritm ei ole midagi muud kui loendi elementide järjestamine kindlasse järjekorda, näiteks madalaimast kõrgeimani väärtus, kõrgeimast madalaim väärtus, järjestuse suurendamine, järjestuse vähendamine, tähestiku järjekord jne. Kõige sagedamini kasutatavad korraldused on numbriline ja leksikograafiline järjekord. Algoritmid kasutavad peamise alamprogrammina sorteerimist. Kõikjal kasutatakse väga erinevaid sortimisalgoritme, milles kõigis rakendatakse rikkalikku tehnikat. Üks selline populaarne, kuid võrdselt võimas algoritm on Divide and Conquer algoritm, mis on mitmeharulisel rekursioonil põhinev algoritm. Kiire sortimine ja ühendamine on kaks kõige sagedamini kasutatavat algoritmi, mis põhinevad jagamise ja vallutamise algoritmil.

Mis on kiire sortimine?

Kiire sortimine on jagamise ja vallutamise lähenemisviisil põhinev ülitõhus, kuid samas tõhus sortimisalgoritm, mis on üsna sarnane dünaamilise lähenemisviisiga, kus probleem jagatakse kaheks või enamaks alamprobleemiks ja lahendatakse seejärel rekursiivselt. Kui alamprobleemid on piisavalt väikesed, lahendatakse need lihtsalt ja arusaadavalt ilma probleemideta. Seda nimetatakse ka partitsioonivahetuse sortimiseks, jaotades kiire sortimise algoritmi sorteeritava nimekirja kolmeks põhiosaks: 1) pöördeelement (kesksed elemendid), 2) elemendid, mis on vähem kui pöördepunktid, ja 3) elemendid, mis on suuremad kui pöördepunkt. Pöördnihk ise viiakse kahe rühma vahel lõplikku asendisse ja seejärel rakendatakse KORRALIK SORT rekursiivselt.

Mis on Merge Sort?

Merge Sort on järjekordne üldotstarbeline sortimisalgoritm, mis põhineb jagamise ja vallutamise tehnikal. See on üks lugupeetumaid ja populaarsemaid sortimisalgoritme, mis on loodud kasutamiseks tõhusalt väliselt faili salvestatud andmete sorteerimiseks. See pakub halvimal juhul O (n log n) käitumist, kui kasutatakse O (n) täiendavat salvestusruumi. See jagab kollektsiooni A kaheks väiksemaks kollektsiooniks, millest igaüks seejärel sorteeritakse. Viimases etapis liidetakse need kaks sorteeritud kollektsiooni tagasi ühte kogusse suurusega n. See on sorteeritud loend. Algoritm on üsna kiire ja ühtlasi ka stabiilne ning on ideaalselt eelistatud lingitud loendite jaoks.

Erinevus kiire sortimise ja liitmise vahel

Põhitõed

- Nii kiire sortimine kui ka ühendamise sortimine on jagamise ja vallutamise põhised sortimisalgoritmid, millel on sama põhiprintsiip - jagada probleem kaheks või enamaks alamprobleemiks ja seejärel need rekursiivselt lahendada. Need erinevad aga ühinemisprotseduuride ja toimivuse osas. Kiire sortimine on üldiselt parem ja kiirem kui muud sortimisalgoritmid, sealhulgas Merge Sort, kui tegemist on väikese andmekogumiga, samas kui Merge Sort säilitab järjepidevuse sõltumata andmekogumite tüübist. Kiire sortimine on ideaalselt eelistatav massiivide jaoks, samas kui Merge Sort on ideaalselt eelistatud linkitud loendite korral.

Ruumi keerukus

- Sorteerimine kiirsorteerimise algoritmis toimub rekursiivselt ja iga rekursiivne kõne nõuab virna paigutamist. See ei vaja ühendamiseks lisaruumi, välja arvatud liitmiseks üksainus mäluruum. Kuna see on kohapealne sorteerimisalgoritm, pole sorteerimiseks lisaruumi vaja. Tegelikult kasutab ta massiivi jagamisel ja liitmisel sama massiivi. Teisest küljest on rakenduses Merge Sort andmeid andmete esitamiseks failina või massiivina mitu moodust, nii et see vajab selliseid tööalasid nagu sama suurusega alamfailid või massiivid, mis vajavad lisaruumi.

Halvim juhtumi keerukus

- Kiire sortimise halvim käitumine ilmneb siis, kui jaotamine on tasakaalust väljas, sõltudes sellest, milliseid elemente partitsioneerimiseks kasutatakse. Sel juhul töötab algoritm asümptootiliselt sama aeglaselt kui sisestamise sorteerimine. Kiire sortimise halvim jõudlus on O (n2) ja see jäetakse treeninguks. Kuid seda saab vältida, kui valite õige pöörde. Merge Sordi halvim juhtum seevastu ilmneb siis, kui ta peab tegema maksimaalse arvu võrdlusi. Arvestades liitmise lineaarset jõudlust, on Merge Sordi halvim jõudlus O (n log2 n).

Etendus

- Ehkki nii kiire sortimise kui ka ühendamise sortimise algoritmid põhinevad sortimisel jagamise ja vallutamise lähenemisviisil, erinevad need jagamise ja liitmisprotseduuride jaoks kasutatud meetodite järgi. Kiire sortimise puhul on suurem osa töö loendi jagamine kaheks alamloendiks, mis toimub enne alamloendite sortimist. Merge Sordi puhul on suurem osa tööst kahe alamloendi ühendamine, mis toimub pärast alamloendite sortimist. Merge Sort nõuab kahe alamassiivi liitmiseks ajutist massiivi, samas kui Quick Sorti jaoks pole vaja täiendavat massiivi ruumi, muutes selle ruumisäästlikumaks kui Marge Sort.

Kiire sortimine ja liitmine: võrdlusdiagramm

Kiire sortimise ja liitmise sortimise kokkuvõte

Nii kiire sortimise kui ka ühendamise sortimise algoritmid põhinevad sortimisel jagamise ja vallutamise lähenemisel. Kuid need erinevad meetodite järgi, mida kasutatakse jagamise ja liitmise protseduuride osas. Nad töötavad põhimõtteliselt samal põhimõttel - jagada probleem kaheks või enamaks alamprobleemiks ja seejärel need rekursiivselt lahendada. Ühendamine on halvemal juhul tõhusam kui kiire sortimine, kuid keskmisel juhul on need kaks sama tõhusad. Kuid Kiire sortimine on ruumisäästlikum kui Merge Sort. Nii et Kiire sortimine on kahtlemata kiirem ja parem kui Merge Sort, kuid see muutub ebatõhusaks mõnes olukorras, näiteks kui võrrelda.

Viited

  • Cormen, Thomas H. jt. Sissejuhatus algoritmidesse. Cambridge, Massachusetts: MIT Press, 2009. Prindi
  • Heineman, George T. jt. Algoritmid lühidalt. Sebastopol, California: O’Reilly Media, 2016. Trükk
  • Mahmoud, Hosam M. Sorteerimine: jaotusteooria. Hoboken, New Jersey: John Wiley & Sons, 2011. Trükk
  • Kujutise krediit: https://upload.wikimedia.org/wikipedia/commons/thumb/e/e6/Merge_sort_algorithm_diagram.svg/500px-Merge_sort_algorithm_diagram.svg.png
  • Kujutise krediit: https://en.wikipedia.org/wiki/Quicksort#/media/File:Quicksort-diagram.svg