de Onel Harrison
Stabilitate în sortarea algoritmilor – un tratament al egalității
Algoritmii se află în centrul informaticii. Algoritmii utilizați pentru sortare sunt unele dintre cele mai fundamentale, utile și, în consecință, omniprezente.
Algoritm – un set finit de pași fără echivoc pentru rezolvarea unei probleme specifice.
În mod constant și deseori, în mod inconștient, sortăm și ne bazăm pe ordinea obiectelor grupate. De exemplu, clasificăm sarcinile pe o listă în funcție de prioritate. Stivuim cărți pe rafturi după înălțimea lor. Sortăm rânduri într-o foaie de calcul sau într-o bază de date sau ne bazăm pe ordinea alfabetică a cuvintelor dintr-un dicționar. Uneori, chiar percepem un anumit fel de frumusețe în aranjamente ordonate.
Ca programatori, știind Cum sortăm este important, deoarece afectează cum ar putea arăta un aranjament sortat. Nu toate felurile comandă obiecte în același mod! Din această cauză, rezultatele operațiilor de sortare diferă în funcție de algoritmii utilizați. Dacă acest lucru nu este recunoscut, ne-am putea surprinde pe noi înșine sau pe cei care folosesc software-ul nostru.
Stabilitatea algoritmilor de sortare este una dintre proprietățile distinctive dintre aceștia. Se ocupă de modul în care algoritmul tratează elemente comparabile cu chei de sortare egale.
Tasta Sortare – O tastă utilizată pentru a determina ordinea articolelor dintr-o colecție, de exemplu vârsta, înălțimea, poziția în alfabet etc.
Un algoritm stabil de sortare menține ordinea relativă a articolelor cu chei de sortare egale. Un algoritm instabil de sortare nu. Cu alte cuvinte, atunci când o colecție este sortată cu un algoritm stabil de sortare, articolele cu aceleași chei de sortare își păstrează ordinea după ce colecția este sortată.
Un exemplu, cod și o demonstrație
Imaginea de mai sus ilustrează efectul unui tip stabil. În stânga, datele au fost sortate alfabetic după nume. După sortarea datelor după clasă, puteți vedea că ordinea alfabetică a numelor a fost menținută pentru fiecare rând cu aceeași notă.
În cazul unei sortări instabile, nu există nicio garanție că ordinea alfabetică este menținută așa cum se arată în imaginea de mai sus.
Nu aveți întotdeauna nevoie de un tip stabil
Este deosebit de important să știți dacă tipul pe care îl utilizați este stabil sau nu. Mai ales în situațiile în care datele dvs. au deja o anumită ordine pe care ați dori să o mențineți atunci când le sortați după o altă cheie de sortare. De exemplu, aveți rânduri într-o foaie de calcul care conține date despre elevi care sunt, în mod implicit, sortate după nume. Ați dori, de asemenea, să o sortați după note, menținând în același timp ordinea sortată a numelor.
Pe de altă parte, stabilitatea sortării nu contează atunci când cheile de sortare ale obiectelor dintr-o colecție sunt obiectele în sine – o matrice de numere întregi sau șiruri, de exemplu – pentru că nu putem face diferența dintre duplicate chei.
// 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']Sortările sunt peste tot – cunoașteți tipurile dvs.
Este destul de ușor să aflați dacă sortarea implicită în limbajul sau biblioteca dvs. de programare este stabilă. Documentația trebuie să includă aceste informații. De exemplu, sortarea implicită este stabilă în Python, instabil în Ruby, și nedefinit? în JavaScript (depinde de implementarea browserului).
Iată câțiva algoritmi de sortare obișnuiți și stabilitatea acestora:
- Sortare prin inserție – stabilă
- Selecție Sortare – Instabilă
- Sortare cu bule – Stabil
- Merge Sort – Stabil
- Sortare Shell – Instabil
- Timsort – Stabil
Vedea Wikipedia pentru o listă mai exhaustivă.
E timpul demo? ?
Această demonstrație arată efectul utilizării unui algoritm stabil (sortare prin inserție) și instabil (sortare prin selecție) pentru a sorta un mic tabel de date. Am avut un pic de distracție și practic React în timp ce construiam acest lucru. Aruncați o privire la sursă.
Ce urmeaza?
Dacă aveți sete de mai multe cunoștințe despre stabilitatea altor algoritmi de sortare, Wikipedia are un tabel de comparație bun și informații suplimentare despre algoritmi de sortare bine cunoscuți.
Până data viitoare, pace.
