Stabiilsus algoritmide sorteerimisel - võrdõiguslikkuse käsitlus

Algoritmid on arvutiteaduse keskmes. Sorteerimiseks kasutatavad algoritmid on ühed kõige fundamentaalsemad, kasulikumad ja järelikult kõikjal levivad.

Algoritm - lõplik komplekt üheselt mõistetavaid samme konkreetse probleemi lahendamiseks.

Me sorteerime pidevalt ja sageli alateadlikult rühmitatud objektide järjekorda. Näiteks reastame loendis ülesanded prioriteedi järgi. Virnastame raamatuid riiulitele nende kõrguse järgi. Sorteerime read arvutustabelis või andmebaasis või tugineme sõnastiku sõnade tähestikulisele järjekorrale. Mõnikord tajume isegi teatud tüüpi ilu tellitud korraldustes.

Programmeerijatena on oluline teada, kuidas me sorteerime, sest see mõjutab seda, kuidas sorditud paigutus võib välja näha. Mitte kõikvõimalikud ei telli esemeid ühtemoodi! Seetõttu erinevad sortimisoperatsioonide tulemused kasutatavate algoritmide põhjal. Kui see jääb teadmata, võime üllatada iseennast või inimesi, kes meie tarkvara kasutavad.

Sortimisalgoritmide stabiilsus on nende üks eristavaid omadusi. See käsitleb seda, kuidas algoritm kohtleb võrreldavaid üksusi võrdsete sortimisvõtmetega.

Sorteerimisklahv - võti, mida kasutatakse kogu üksuste järjestuse määramiseks, nt vanus, kõrgus, tähestiku asukoht jne.

Stabiilne sortimisalgoritm hoiab võrdsete sortimisvõtmetega üksuste suhtelist järjestust. Ebastabiilne sortimisalgoritm mitte. Teisisõnu, kui kogu on sorteeritud stabiilse sortimisalgoritmiga, säilitavad samade sortimisvõtmetega üksused oma järjestuse ka pärast kogu sortimist.

Näide, kood ja demo

Ülaltoodud pilt illustreerib stabiilse sortimise mõju. Vasakul olid andmed sorteeritud tähestiku järgi nime järgi. Pärast andmete sorteerimist hinde järgi näete, et nimede tähestikuline järjestus säilitati sama reaga igas reas.

Ebastabiilse sorteerimise korral ei saa garanteerida, et tähestikuline järjestus säiliks nagu ülaltoodud pildil näidatud.

Alati pole vaja stabiilset sorti

Eriti oluline on teada, kas teie kasutatav sort on stabiilne või mitte. Eriti olukordades, kus teie andmetel on juba mingi järjekord, mida soovite säilitada, kui sortite need mõne muu sortimisvõtme järgi. Näiteks on teil tabelis read, mis sisaldavad õpilaste andmeid, mis on vaikimisi sorteeritud nime järgi. Samuti soovite selle sortida hinnete järgi, säilitades nimede järjestuse.

Teisest küljest pole sordi stabiilsusel mingit tähtsust, kui kollektsiooni objektide sortimisvõtmed on objektid ise - näiteks täisarvude või stringide massiiv -, kuna me ei suuda dubleeritavate vahel vahet teha võtmeid.

// JavaScript
// $5 bucks if you can correctly tell which 4 in the sorted// array was the first 4 when the array was unsorted.
var numbers = [5, 4, 3, 4, 9];numbers.sort(); // [3, 4, 4, 5, 9]
// A one second trip around the world, courtesy of the Flash, to// whomever correctly tells me which 'harry' in the sorted array was// the second 'harry' in the unsorted array.
var names = ['harry', 'barry', 'harry', 'cisco'];names.sort(); // ['barry', 'cisco', 'harry', 'harry']

Sorte on igal pool - tea oma sorte

On üsna lihtne teada saada, kas vaikimisi sortimine teie programmeerimiskeeles või teegis on stabiilne. Dokumentatsioon peaks sisaldama seda teavet. Näiteks on vaikesorteerimine Pythonis stabiilne, Ruby's ebastabiilne ja määratlemata? JavaScripti (see sõltub brauseri rakendusest).

Siin on mõned levinumad sortimisalgoritmid ja nende stabiilsus:

  • Lisamise sortimine - stabiilne
  • Valiku sortimine - ebastabiilne
  • Mullide sortimine - stabiilne
  • Ühenda sortimine - stabiilne
  • Kesta sortimine - ebastabiilne
  • Timsort - stabiilne

Põhjalikuma loendi leiate Vikipeediast.

On demo aeg? ‍?

See demo näitab stabiilse (sisestamise sortimise) ja ebastabiilse sorteerimise (valiku sortimise) algoritmi kasutamise mõju väikese andmetabeli sortimiseks. Mul oli selle ehitamise ajal natuke lõbus ja praktiliselt tagurpidi konstrueeritud React. Heitke pilk allikale.

Mis järgmiseks?

Kui teil on janu saada rohkem teadmisi teiste sortimisalgoritmide stabiilsuse kohta, on Vikipeedias hea võrdlustabel ja lisateave tuntud sorteerimisalgoritmide kohta.

Järgmise korrani rahu.

Õppisite midagi uut või meeldis seda artiklit lugeda? Plaksutama?, Jagage seda, et ka teised saaksid lugeda, ja järgige lisateavet. Jäta julgelt ka kommentaar.