Algoritmide sorteerimine selgitatud

Sorteerimisalgoritmid on käskude kogum, mis võtab sisendina massiivi või loendi ja korraldab üksused kindlas järjekorras.

Sordid on kõige sagedamini numbrilises või tähestikulises (nn leksikograafilises) järjekorras ning võivad olla kasvavas (AZ, 0–9) või kahanevas (ZA, 9–0) järjekorras.

Miks on algoritmide sorteerimine oluline?

Kuna sortimine võib sageli probleemi keerukust vähendada, on see arvutiteaduses oluline algoritm. Nendel algoritmidel on otseseid rakendusi algoritmide, andmebaaside algoritmide, jagamise ja vallutamise meetodite, andmestruktuuri algoritmide ja palju muu otsimisel.

Mõned levinumad sortimisalgoritmid

Mõned kõige levinumad sortimisalgoritmid on:

  • Valik Sorteeri
  • Mullide sortimine
  • Sisestuse sortimine
  • Ühenda sortimine
  • Kiire sortimine
  • Hunnik Sorteeri
  • Loendamine Sorteeri
  • Radix Sorteeri
  • Ämber Sorteeri

Sorteerimisalgoritmi klassifikatsioon

Sortimisalgoritme saab kategoriseerida järgmiste parameetrite alusel:

  1. Põhineb vahetuste arvul või inversioonil See on algoritmi elementide sisendi sortimiseks vahetamise arv. Selection Sortnõuab minimaalset vahetustehingute arvu.
  2. Põhineb võrdluste arv See on mitu korda algoritm võrdleb elemente sisendi sortimiseks. Kasutades Big-O tähistust, vajavad ülalpool loetletud sorteerimisalgoritmide näited O(nlogn)parimal juhul vähemalt võrdlemist ja O(n^2)halvimal juhul enamiku väljundite võrdlemist.
  3. Rekursioonil või mitterekursioonil põhinevad Mõned sortimisalgoritmid, näiteks Quick Sortkasutavad sisendi sorteerimiseks rekursiivseid tehnikaid. Teised sorteerimisalgoritmid, näiteks Selection Sortvõi Insertion Sort, kasutavad mitte-rekursiivseid tehnikaid. Lõpuks kasutavad mõned sorteerimisalgoritmid, näiteks Merge Sortsisendi sorteerimiseks nii rekursiivseid kui ka mitterekursiivseid tehnikaid.
  4. Põhineb stabiilsusel. Sortimisalgoritmid on väidetavalt siis, stablekui algoritm säilitab võrdsete klahvidega elementide suhtelise järjekorra. Teisisõnu, kaks samaväärset elementi jäävad järjestatud väljundis samas järjekorras nagu nad olid sisendis.
  5. Insertion sort, Merge SortJa Bubble Sorton stabiilsed
  6. Heap Sortja Quick Sortei ole stabiilsed
  7. Põhineb ekstra ruumivajadusel väidetavalt on sorteerimisalgoritmid juhul, in placekui nende O(1)sortimiseks on vaja püsivat lisaruumi.
  8. Insertion sortja Quick-sorton in placesorteeritavad, kui liigutame elemente pöördetapi ümber, ja tegelikult ei kasuta eraldi massiivi, mida EI juhtu liidetud sortimisel, kus sisendi suurus tuleb sortimise ajal väljundi salvestamiseks eelnevalt eraldada.
  9. Merge Sorton out placesortimise näide, kuna see nõuab toiminguteks täiendavat mäluruumi.

Parim ajaline keerukus võrdluspõhise sortimise jaoks

Mis tahes võrdluspõhine sortimisalgoritm peab sisendmassiivi sorteerimiseks tegema vähemalt nLog2n võrdlused ning Heapsorti ja liitmise sortimine on asümptootiliselt optimaalsed võrdlussordid. Seda saab hõlpsasti tõestada otsustuspuu skeemi joonistamisega.