Stabilumas rūšiuojant algoritmus - požiūris į lygybę

Algoritmai yra kompiuterių mokslo pagrindas. Rūšiavimui naudojami algoritmai yra vieni svarbiausių, naudingiausių, taigi ir visur esančių.

Algoritmas - baigtinis nedviprasmiškų veiksmų rinkinys konkrečiai problemai spręsti.

Mes nuolat ir dažnai nesąmoningai rūšiuojame ir remiamės sugrupuotų objektų tvarka. Pvz., Sąraše užduotis suskirstome pagal prioritetus. Krauname knygas į lentynas pagal jų aukštį. Rūšiuojame eilutes skaičiuoklėje arba duomenų bazėje arba pasikliaujame žodžių abėcėlės tvarka. Kartais mes netgi suvokiame tam tikrą grožį pagal užsakymą.

Kaip programuotojai, svarbu žinoti, kaip mes rūšiuojame, nes tai turi įtakos tam, kaip gali atrodyti rūšiuojama tvarka. Ne visokie objektai užsakomi vienodai! Dėl to rūšiavimo operacijų rezultatai skiriasi pagal naudojamus algoritmus. Jei tai nebus pripažinta, galime nustebinti save ar žmones, kurie naudojasi mūsų programine įranga.

Rūšiavimo algoritmų stabilumas yra viena iš jų skiriamųjų savybių. Jis nagrinėja, kaip algoritmas traktuoja palyginamus elementus vienodais rūšiavimo klavišais.

Rūšiavimo klavišas - raktas, naudojamas nustatyti prekių kolekcijos eiliškumą, pvz., Amžių, ūgį, padėtį abėcėlėje ir kt.

Stabilus rūšiavimo algoritmas palaiko santykinę elementų tvarką vienodais rūšiavimo klavišais. Nestabilus rūšiavimo algoritmas to nedaro. Kitaip tariant, kai kolekcija yra rūšiuojama naudojant stabilų rūšiavimo algoritmą, elementai, turintys tuos pačius rūšiavimo raktus, išsaugo savo tvarką po kolekcijos rūšiavimo.

Pavyzdys, kodas ir demonstracinė versija

Aukščiau pateiktas vaizdas iliustruoja stabilios rūšiavimo efektą. Kairėje duomenys buvo rūšiuojami abėcėlės tvarka pagal pavadinimą. Surūšiavus duomenis pagal klasę, galite pamatyti, kad abėcėlės tvarka buvo išlaikyta kiekvienos eilės su tuo pačiu pažymiu eilutė.

Esant nestabiliam rūšiavimui, nėra jokios garantijos, kad abėcėlės tvarka bus išlaikyta taip, kaip parodyta aukščiau esančiame paveikslėlyje.

Jums ne visada reikia stabilaus rūšiavimo

Ypač svarbu žinoti, ar jūsų naudojama rūšis yra stabili. Ypač tais atvejais, kai jūsų duomenys jau turi tam tikrą tvarką, kurią norėtumėte išlaikyti rūšiuodami pagal kitą rūšiavimo raktą. Pavyzdžiui, skaičiuoklėje yra eilučių, kuriose yra studentų duomenys, kurie pagal numatytuosius nustatymus yra rūšiuojami pagal vardą. Jūs taip pat norėtumėte rūšiuoti pagal pažymius, išlaikydami išrūšiuotą vardų tvarką.

Kita vertus, rūšiavimo stabilumas nėra svarbus, kai kolekcijos objektų rūšiavimo klavišai yra patys objektai - pavyzdžiui, sveikųjų skaičių ar eilučių masyvas, nes mes negalime pasakyti skirtumo tarp pasikartojančių objektų raktai.

// 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']

Rūšių yra visur - žinok savo rūšis

Gana lengva sužinoti, ar numatytasis rūšiavimas jūsų programavimo kalboje ar bibliotekoje yra stabilus. Dokumentuose turėtų būti ši informacija. Pavyzdžiui, numatytasis rūšiavimas yra stabilus „Python“, nestabilus „Ruby“ ir neapibrėžtas? „JavaScript“ (tai priklauso nuo naršyklės diegimo).

Štai keli įprasti rūšiavimo algoritmai ir jų stabilumas:

  • Įterpimo rūšiavimas - stabilus
  • Pasirinkimo rūšiavimas - nestabilus
  • Burbulų rūšiavimas - stabilus
  • Sujungti rūšiavimą - stabilus
  • Korpuso rūšiavimas - nestabilus
  • Timsortas - stabilus

Išsamesnį sąrašą rasite Vikipedijoje.

Atėjo demonstracinis laikas? ‍?

Ši demonstracinė versija rodo stabilaus (įterpimo rūšiavimo) ir nestabilaus rūšiavimo (pasirinkimo rūšiavimo) algoritmo naudojimo efektą mažai duomenų lentelei rūšiuoti. Šiek tiek smagiai ir praktiškai sukonstravau „React“, kai tai kūriau. Pažvelkite į šaltinį.

Kas toliau?

Jei ištroškote daugiau žinių apie kitų rūšiavimo algoritmų stabilumą, „Wikipedia“ turi gerą palyginimo lentelę ir papildomos informacijos apie gerai žinomus rūšiavimo algoritmus.

Iki kito karto - ramybė.

Sužinojai ką nors naujo ar patiko skaityti šį straipsnį? Plokštelėk?, Dalinkis, kad ir kiti galėtų skaityti, ir seki toliau. Nedvejodami palikite komentarą.