Stabilitás az algoritmusok rendezésében - Az egyenlőség kezelése

Az algoritmusok a számítástechnika középpontjában állnak. A válogatáshoz használt algoritmusok a legalapvetőbbek, a leghasznosabbak, következésképpen mindenütt jelen vannak.

Algoritmus - egy meghatározott probléma megoldásának egyértelmű lépései.

Folyamatosan és gyakran öntudatlanul válogatunk és támaszkodunk a csoportosított tárgyak sorrendjére. Például rangsoroljuk a feladatokat a listán prioritás szerint. Könyveket rakunk polcokra magasságuk szerint. Sorokat rendezünk egy táblázatban vagy adatbázisban, vagy támaszkodunk a szótárak ábécé szerinti sorrendjére. Néha még egyfajta szépséget is érzékelünk rendezett elrendezésekben.

Ahogy a programozók, tudván , hogy hogyan tudjuk a fajta fontos, mert befolyásolja, amit egy rendezett elrendezését nézhet. Nem mindenféle rendel egyforma tárgyakat! Emiatt a rendezési műveletek eredményei eltérnek az alkalmazott algoritmusoktól. Ha ezt nem ismerjük el, meglepetést okozhatunk magunkon vagy azokon az embereken, akik a szoftverünket használják.

A rendezési algoritmusok stabilitása az egyik megkülönböztető tulajdonság közöttük. Foglalkozik azzal, hogy az algoritmus miként kezeli az összehasonlítható elemeket azonos rendezési kulcsokkal.

Rendezési kulcs - A gyűjteményben található elemek sorrendjének meghatározásához használt kulcs, pl. Életkor, magasság, ábécében elfoglalt hely stb.

A stabil rendezési algoritmus fenntartja az elemek relatív sorrendjét azonos rendezési kulcsokkal. Az instabil rendezési algoritmus nem. Más szavakkal, ha egy gyűjteményt stabil rendezési algoritmussal rendeznek, az azonos rendezési kulcsokkal rendelkező elemek megőrzik sorrendjüket a gyűjtemény rendezése után.

Példa, kód és bemutató

A fenti kép szemlélteti a stabil rendezés hatását. A bal oldalon az adatokat ábécé sorrendben rendeztük Név szerint. Az adatok fokozat szerinti rendezése után láthatja, hogy a nevek ábécé sorrendje megmaradt minden sorhoz ugyanazzal az osztályzattal.

Az instabil rendezésnél nincs garancia arra, hogy az ábécé sorrendje a fenti képen látható módon fennmaradjon.

Nem mindig van szüksége stabil rendezésre

Különösen fontos tudni, hogy a használt rendezés stabil-e vagy sem. Különösen azokban a helyzetekben, amikor az adatok már vannak olyan sorrendben, amelyeket fenntartani szeretne, ha más rendezési kulcs szerint rendezi. Például egy táblában sorok vannak a hallgatói adatokkal, amelyek alapértelmezés szerint név szerint vannak rendezve. Szeretné osztályozni osztályzatok szerint is, miközben megtartja a nevek rendezett sorrendjét.

Másrészt a rendezés stabilitása nem számít, ha a gyűjteményben lévő objektumok rendezési kulcsai maguk az objektumok - például egész számok vagy karakterláncok tömbje -, mert nem tudunk különbséget tenni a másolatok között kulcsok.

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

A fajta mindenhol megtalálható - ismerje a fajtáját

Nagyon könnyű kideríteni, hogy a programozási nyelv vagy könyvtár alapértelmezett rendezése stabil-e. A dokumentációnak tartalmaznia kell ezeket az információkat. Például az alapértelmezett rendezés a Pythonban stabil, a Rubyban instabil és undefined? JavaScript-ben (ez a böngésző megvalósításától függ).

Íme néhány általános rendezési algoritmus és azok stabilitása:

  • Beszúrási rendezés - stabil
  • Kiválasztás rendezése - instabil
  • Bubble Sort - stabil
  • Egyesítés rendezése - stabil
  • Shell Sort - instabil
  • Timsort - stabil

A teljesebb listát lásd a Wikipédiában.

Itt a bemutató ideje? ‍?

Ez a bemutató azt mutatja be, hogy milyen hatással van egy stabil (beszúrási rendezés) és instabil rendezés (kiválasztás rendezése) algoritmus egy kis adattábla rendezésére. Kicsit szórakoztam és gyakorlatilag visszafejtettem a React-et ennek felépítése közben. Nézd meg a forrást.

Mi a következő lépés?

Ha további információra vágyik más rendezési algoritmusok stabilitásáról, a Wikipedia jó összehasonlító táblázatot és további információkat tartalmaz a jól ismert rendezési algoritmusokról.

Legközelebb béke.

Tanultál valami újat, vagy szívesen olvastad ezt a cikket? Csapd össze ?, oszd meg, hogy mások is olvashassanak, és kövessék tovább. Nyugodtan írj megjegyzést is.