Conţinutul principal
Biblioteca de informatică
Curs: Biblioteca de informatică > Unitatea 1
Lecția 7: Sortarea prin interclasarePrezentare generală a sortării prin îmbinare
Deoarece folosim divide et impera pentru sortare, trebuie să decidem cum arată subproblemele noastre. Problema inițială este sortarea unui întreg vector. Să spunem că o subproblemă este sortarea unui subșir din vector. Concret, ne vom gândi la o subproblemă ca fiind sortarea subșirului care începe de la poziția p și se termină la poziția r. Este convenabil să alegem o notație pentru un subșir, așa că vom scrie
array[p..r]
pentru un subșir al vectorului array
. Trebuie să ai în vedere că scrierea cu „două puncte” nu face parte din JavaScript; o folosim doar pentru a descrie algoritmul, nu pentru a scrie cod. Pe baza notației noastre, pentru un vector cu n elemente, putem spune că problema inițială este sortarea lui array[0..n-1]
.Iată cum sortarea prin interclasare folosește divide et impera:
- Divide prin găsirea poziției q aflată la jumătatea distanței dintre p și r. Repetă acest pas și găsește mijlocul în mod asemănător cu algoritmul căutării binare: adună p și r, împarte la 2 și rotunjește inferior.
- Rezolvă prin sortarea recursivă a subșirurilor din cele două subprobleme create de pasul care divide, adică sortează recursiv subșirurile
array[p..q]
șiarray[q+1..r]
. - Asamblează prin interclasarea celor două subșiruri sortate într-un singur subșir sortat
array[p..r]
.
Avem nevoie de un caz de bază. Cazul de bază este un subșir ce conține mai puțin de două elemente, adică are proprietatea p, is greater than or equal to, r, din moment ce un subșir cu niciun element sau cu un singur element este deja sortat. Așadar, vom aplica divide et impera doar atunci când p, is less than, r.
Haide să vedem un exemplu. Să începem cu un vector
array
care are elementele [14, 7, 3, 12, 9, 11, 6, 2], iar subșirul său inițial este chiar întregul vector, array[0..7]
(p, equals, 0 și r, equals, 7). Acest subșir are cel puțin două elemente, deci nu reprezintă un caz de bază.- În etapa divide găsim q, equals, 3.
- Etapa rezolvă ne impune să sortăm cele două subșiruri:
array[0..3]
, cu elementele [14, 7, 3, 12] șiarray[4..7]
, cu elementele [9, 11, 6, 2]. Când finalizăm această etapă, cele două subșiruri sunt sortate:array[0..3]
conține [3, 7, 12, 14] șiarray[4..7]
conține [2, 6, 9, 11], așadar întregul vector este [3, 7, 12, 14, 2, 6, 9, 11]. - În final, etapa asamblează interclasează cele două subșiruri sortate și generează vectorul sortat [2, 3, 6, 7, 9, 11, 12, 14].
Cum a fost sortat subșirul
array[0..3]
? În același mod. Are mai mult de două elemente, deci nu reprezintă un caz de bază. Cu p, equals, 0 și r, equals, 3, găsim q, equals, 1, sortăm recursiv array[0..1]
([14, 7]) și array[2..3]
([3, 12]) și obținem array[0..3]
ce conține [7, 14, 3, 12], apoi interclasăm prima jumătate cu cea de-a doua și rezultă [3, 7, 12, 14].Cum a fost sortat subșirul
array[0..1]
? Cu p, equals, 0 și r, equals, 1, găsim q, equals, 0, sortăm recursiv array[0..0]
([14]) și array[1..1]
([7])și obținem array[0..1]
ce conține tot [14, 7], apoi interclasăm prima jumătate cu cea de-a doua și rezultă [7, 14].Subșirurile
array[0..0]
și array[1..1]
sunt cazuri de bază, din moment ce fiecare conține mai puțin de două elemente. Iată cum se desfășoară întregul algoritm al sortării prin interclasare:Majoritatea pașilor sortării prin interclasare sunt simpli. Poți verifica ușor cazul de bază. Găsirea mijlocului q în etapa care divide se face cu ușurință. Trebuie să faci două apeluri recursive în etapa de rezolvare. Etapa de asamblare în care trebuie să interclasezi două subșiruri sortate este cea mai importantă.
În următoarea provocare, te vei concentra pe implementarea algoritmului general de sortare prin interclasare, pentru a fi sigur că înțelegi cum să aplici divide et impera recursiv. Apoi vom analiza mai atent modul în care putem interclasa în mod eficient două subșiruri sortate şi vei implementa și acest algoritm într-o provocare ulterioară.
Acest conținut este o colaborare a profesorilor Thomas Cormen și Devin Balkcom, de la Dartmouth Computer Science, cu echipa de elaborare a curriculumului de informatică a Khan Academy. Conținutul este licențiat CC-BY-NC-SA.
Vrei să te alături conversației?
Nici o postare încă.