Razloženi algoritmi za razvrščanje

Algoritmi za razvrščanje so nabor navodil, ki za vnos vzamejo matriko ali seznam in razvrstijo elemente v določen vrstni red.

Sorte so najpogosteje v številčnem ali abecednem (tako imenovanem leksikografskem) vrstnem redu in so lahko naraščajoče (AZ, 0-9) ali padajoče (ZA, 9-0).

Zakaj so algoritmi razvrščanja pomembni

Ker lahko razvrščanje pogosto zmanjša zapletenost problema, je to pomemben algoritem v računalništvu. Ti algoritmi imajo neposredno uporabo pri iskanju algoritmov, algoritmih baz podatkov, metodah deljenja in osvajanja, algoritmih podatkovne strukture in mnogih drugih.

Nekaj ​​pogostih algoritmov za razvrščanje

Nekateri najpogostejši algoritmi za razvrščanje so:

  • Razvrsti razvrstitev
  • Razvrstitev mehurčkov
  • Razvrstitev vstavka
  • Združi razvrsti
  • Hitro razvrščanje
  • Razvrsti kup
  • Razvrščanje štetja
  • Radix Razvrsti
  • Razvrsti vedro

Klasifikacija sortirnega algoritma

Algoritme za razvrščanje lahko razvrstimo na podlagi naslednjih parametrov:

  1. Glede na število zamenjav ali inverzije To je, kolikokrat algoritem zamenja elemente, da razvrsti vhod. Selection Sortzahteva minimalno število zamenjav.
  2. Glede na število primerjav To je, kolikokrat algoritem primerja elemente za razvrščanje vhodnih podatkov. Z uporabo zapisov Big-O zgoraj našteti primeri algoritmov za razvrščanje zahtevajo vsaj O(nlogn)primerjave v najboljšem primeru in O(n^2)primerjave v najslabšem primeru za večino izhodov.
  3. Na podlagi rekurzije ali nerekurzije Nekateri algoritmi za razvrščanje, na primer Quick Sort, uporabljajo rekurzivne tehnike za razvrščanje vnosa. Drugi algoritmi za razvrščanje, na primer Selection Sortali Insertion Sort, uporabljajo nerekurzivne tehnike. Na koncu nekateri algoritmi za razvrščanje, na primer Merge Sort, za razvrščanje vnosa uporabljajo tako rekurzivne kot tudi nerekurzivne tehnike.
  4. Algoritmi za razvrščanje na podlagi stabilnosti naj bi veljali, stableče algoritem ohranja relativni vrstni red elementov z enakimi ključi. Z drugimi besedami, dva enakovredna elementa ostaneta v razvrščenem izhodu v enakem vrstnem redu kot v vhodu.
  5. Insertion sort, Merge SortIn Bubble Sortso stabilne
  6. Heap Sortin Quick Sortniso stabilne
  7. Na podlagi zahteve in placepo O(1)dodatnem prostoru naj bi algoritmi za razvrščanje veljali, če za razvrščanje potrebujejo stalen dodaten prostor.
  8. Insertion sortin Quick-sortso in placerazvrščeni, ko premikamo elemente okoli vrtišča, in dejansko ne uporabljamo ločene matrike, kar NI v primeru združevanja, kjer je treba vnaprej dodeliti velikost vhoda za shranjevanje izhoda med razvrščanjem.
  9. Merge Sortje primer out placerazvrščanja, saj za svoje delovanje potrebuje dodaten pomnilniški prostor.

Najboljša možna časovna zapletenost za vsako razvrščanje na podlagi primerjave

Vsak algoritem za razvrščanje na podlagi primerjave mora opraviti vsaj primerjave nLog2n, da razvrsti vhodno matriko, razvrščanje po sorti in združevanje pa sta asimptotično optimalni sorti primerjave, kar lahko enostavno dokažemo z risanjem diagrama odločitvenega drevesa.