Conţinutul principal
Biblioteca de informatică
Curs: Biblioteca de informatică > Unitatea 1
Lecția 7: Sortarea prin interclasare- Algoritmi Divide-et-Impera
- Prezentare generală a sortării prin interclasare (îmbinare)
- Provocare: Implementează sortarea prin îmbinare
- Îmbinarea în timp liniar
- Provocare: Implementează îmbinarea
- Analiza sortării prin îmbinare
© 2023 Khan AcademyCondiții de utilizarePolitica de confidenţialitateNotificare Cookie
Prezentare generală a sortării prin interclasare (î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 și se termină la poziția . Este convenabil să alegem o notație pentru un subșir, așa că vom scrie elemente, putem spune că problema inițială este sortarea lui
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 array[0..n-1]
.Iată cum sortarea prin interclasare folosește divide et impera:
- Divide prin găsirea poziției
aflată la jumătatea distanței dintre și . Repetă acest pas și găsește mijlocul în mod asemănător cu algoritmul căutării binare: adună și , împarte la 2 și rotunjește prin lipsă. - Rezolvă prin sortarea recursivă a subșirurilor din cele două subprobleme create la pasul de împărțire (divide), adică sortează recursiv subșirurile
array[p..q]
șiarray[q+1..r]
. - Combină soluțiile prin interclasarea celor două subșiruri sortate într-un singur subșir sortat
array[p..r]
.
Avem nevoie de un caz elementar (de bază). Cazul elementar este un subșir ce conține mai puțin de două elemente, adică are proprietatea , 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 .
Hai să vedem un exemplu. Să începem cu un vector și ). Acest subșir are cel puțin două elemente, deci nu reprezintă un caz elementar.
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]
(- În etapa divide găsim
. - 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, la etapa combină, interclasăm cele două subșiruri sortate și generăm vectorul sortat [2, 3, 6, 7, 9, 11, 12, 14].
Cum a fost sortat subșirul și , găsim , sortăm recursiv
array[0..3]
? În același mod. Are mai mult de două elemente, deci nu reprezintă un caz elementar. Cu 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 și , găsim , sortăm recursiv
array[0..1]
? Cu 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 elementare (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 elementar (de bază). Găsirea mijlocului în etapa divide (de împărțire) se face cu ușurință. Trebuie să faci două apeluri recursive în etapa de rezolvare. Etapa de combinare în care trebuie să interclasezi două subșiruri sortate este cea mai solicitantă.
Î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ă de la Khan Academy. Conținutul este licențiat CC-BY-NC-SA.
Vrei să te alături conversației?
Nici o postare încă.