de Yung L. Leung

O introducere in algoritmii de sortare avansati fuzionare sortare rapida
Ilustrație de Marc Lariviere pe Giphy

În articolul meu anterior, „Complexitatea algoritmilor simpli și structurilor de date în JavaScript”, Am discutat despre algoritmi simpli de sortare (sortare cu bule, selecție și inserare). Aici, trec combina, rapid & sortare radix, fiecare dintre acestea are o îmbunătățire semnificativă asupra in medie complexitatea timpului, mai puțin decât O (n²).

Să parcurgem fiecare dintre acestea mai detaliat.

Combina

A fuzionează sort separă o listă în articolele sale individuale. Apoi le sortează pe măsură ce sunt fuzionate într-o listă ordonată în creștere.

1611552246 150 O introducere in algoritmii de sortare avansati fuzionare sortare rapida
sursă

În practică, aceasta ar însemna tăierea continuă a unui tablou în matrici cu elemente unice, înainte de împingerea fiecărui element într-un tablou mai mare (prima valoare mai mică). Fiecare etapă de împingere a elementelor din 2 matrice mai mici într-o matrice mai mare implică determinarea elementului din care matrice are valoarea mai mică.

ad-banner

Complexitatea sortării fuziunii este O ((n log n) + 1). Amintiți-vă că notația Big O (Complexitatea algoritmilor simpli și structurilor de date în JS) este un număr al numărul de operațiuni (O) Cu respect catre numărul de elemente (n). Deci, o listă cu 4 elemente necesită 3 împărțiri. Notă, lista este deja comandată pentru simplitatea exemplului.

O introducere in algoritmii de sortare avansati fuzionare sortare rapida
Împărțirea unei liste cu 4 elemente.

Combinarea celor 4 matrice necesită 6 comparații.

1611552247 29 O introducere in algoritmii de sortare avansati fuzionare sortare rapida
Odată divizate, pe măsură ce sunt fuzionate, cele 4 elemente necesită un total de 6 comparații.

Deci, calculul matematic este după cum urmează:

1611552247 953 O introducere in algoritmii de sortare avansati fuzionare sortare rapida
9 operațiuni (3 divizări și 6 comparații) sunt necesare pentru a efectua o sortare de îmbinare pe o matrice de 4 elemente

Pentru simplitate, complexitatea sortării fuziunii este O (n jurnal n). +1 este nesemnificativ în raport cu valoarea n log n și se presupune baza log 2.

Rapid

A sortare rapida selectează o valoare (la index 0), schimbă toate valorile mai mici mai aproape de ea, apoi face un swap final pentru a plasa valoarea selectată înaintea valorilor mai mici (un index undeva după 0). În acest mod, toate valorile din spatele valoarea pivotului sunt valori mai mici. Toate valorile dinaintea ei sunt valori mai mari. Prin urmare, la pivotare, valoarea selectată (pivot) este plasat în poziția corectă. Procesul se repetă până când toate valorile sunt „pivotate” în pozițiile lor corecte.

1611552247 120 O introducere in algoritmii de sortare avansati fuzionare sortare rapida
sursă

Similar în practică cu fuzionează sortarea, sortare rapida necesită împărțirea unei liste în liste mai mici. Mai degrabă decât sortarea la îmbinare, este selectat un pivot pentru a ordona lista astfel încât valori mai mici să fie la stânga și valori mai mari să fie la dreapta. Prin urmare, nu este o surpriză faptul că, cum ar fi fuzionează sort, sortare rapida are, de asemenea, o complexitate de O (n jurnal n).

Deci, pentru o matrice cu 4 elemente, este selectat un pivot și se găsește poziția sa corectă (adică 2 la indexul 0 aparține la indexul 1). În timpul acestei descoperiri, se fac 3 comparații cu valoarea pivotului (2) cu elementele rămase (4, 1 și 3).

1611552248 478 O introducere in algoritmii de sortare avansati fuzionare sortare rapida
Sortare rapidă a matricei [2, 4, 1, 3]

Matricea parțial sortată (1, 2, 4, 3) este apoi descompusă pentru a găsi pozițiile de pivotare a valorii 1 și 4 (prin comparație cu valoarea 3), înainte de a descoperi ultima poziție de pivot (valoare 3). Aceasta înseamnă 4 comparații și descoperirea a 4 poziții pivot sau:

1611552248 412 O introducere in algoritmii de sortare avansati fuzionare sortare rapida
O (n jurnal n)

Radix

A sortare radix comandă continuu o listă de numere în funcție de zece cifre.

1611552248 510 O introducere in algoritmii de sortare avansati fuzionare sortare rapida
Cifre de la 0 la 9

În acest caz, numerele (101, 54, 305, 6, 81) sunt ordonate mai întâi după cifra lor de 0, apoi, cifra de 10 și în cele din urmă, cifra de 100. În practică, aceasta înseamnă crearea de găleți (cifre de la 0 la 9) pentru stocarea numerelor cu cifre comune (adică 101 & 81 are o cifră comună la locul lui 0). Apoi, combinând toate numerele în ordinea lor de găleată (începând cu locul 0: 101, 81, 54, 305, 6), înainte de a repeta procesul cu cifrele locului 10. Aceasta continuă până când sunt atinse cele mai mari cifre plasate (adică 101 & 305 au cifrele locului 100).

În general, complexitatea sortare radix este OK n).

  • n este numărul de elemente
  • k este numărul mediu de cifre pe element

Cantitatea de numere de sortat (n) este de câte ori este necesar pentru a face depozite în aceste găleți de cifre. Deci lista de 101, 54, 305, 6, 81 necesită cel puțin 5 depozite. Cu cât cifrele sunt mai mari (k) din colecția de numere, cu atât mai multe ori este necesar să se repete procesul de sortare de la 0, 10, 100, 1000, etc. Deci lista 101, 54, 305, 6, 81 necesită 5 depozite pentru 0, Anii 10 & 100 loc. Asta înseamnă un total de 3 x 5 = 15 depozite.

Concluzie

Învățarea algoritmilor avansați nu diminuează importanța celor mai de bază. Prin studierea algoritmilor de bază, veți afla despre ce înseamnă să căutați sau să sortați, pur și simplu. Și din acest studiu, puteți începe să înțelegeți problemele care vin cu acești algoritmi de bază.

Nimic nu este creat în vid. Începe cu o idee. De unde merge de acolo este limitat de mintea umană și de ceea ce putem face cu lumea fizică din jurul nostru. Este „întotdeauna prima zi”, dacă alegeți să vă extindeți orizontul.

Referinţă:

https://www.udemy.com/js-algorithms-and-data-structures-masterclass/