Conţinutul principal
Biblioteca de informatică
Curs: Biblioteca de informatică > Unitatea 1
Lecția 7: Sortarea prin interclasareÎmbinarea în timp liniar
Ultimul pas al sortării prin interclasare este funcția
merge
, care interclasează două subșiruri adiacente sortate, array[p..q]
și array[q+1..r]
, rezultând un singur subșir sortat array[p..r]
. Vom vedea cum putem proiecta această funcție pentru a fi cât mai eficientă. Să presupunem că cele două subșiruri au în total n elemente. Trebuie să analizăm fiecare element pentru a interclasa șirurile, așadar cel mai scurt timp de execuție pe care îl putem obține pentru interclasare este egal cu \Theta, left parenthesis, n, right parenthesis. Într-adevăr, vom vedea cum putem interclasa n elemente în \Theta, left parenthesis, n, right parenthesis timp.Pentru a interclasa subșirurile sortate
array[p..q]
și array[q+1..r]
, salvând rezultatul în array[p..r]
, mai întâi trebuie să creăm niște subșiruri temporare în care să copiem array[p..q]
and array[q+1..r]
. Nu putem suprarscrie șirul array[p..r]
până când nu memorăm în altă parte elementele din array[p..q]
și array[q+1..r]
.Așadar, prima etapă din funcția
merge
constă în alocarea celor două subșiruri temporare, lowHalf
și highHalf
, pentru a copia elementele din array[p..q]
în lowHalf
și elementele din array[q+1..r]
în highHalf
. Ce dimensiune ar trebui să aibă lowHalf
? Subșirul array[p..q]
conține q, minus, p, plus, 1 elemente. Dar highHalf
? Subșirul array[q+1..r]
conține r, minus, q elemente. (În JavaScript nu trebuie să specificăm dimensiunea vectorului la declarare, dar pentru că trebuie să facem acest lucru în multe alte limbaje de programare, luăm acest pas în considerare atunci când descriem un algoritm.)În exemplul nostru, [14, 7, 3, 12, 9, 11, 6, 2], iată cum arată lucrurile după ce am sortat recursiv
array[0..3]
și array[4..7]
(astfel încât p, equals, 0, q, equals, 3, și r, equals, 7) și după ce am copiat aceste subșiruri în lowHalf
și highHalf
:Numerele din
array
sunt colorate cu gri pentru a indica faptul că deși indicii vectorului conțin valori, „adevăratele” valori se află acum în lowHalf
și highHalf
. Putem suprascrie numerele gri după bunul plac.În continuare, interclasăm cele două subșiruri sortate, aflate acum în
lowHalf
și highHalf
, înapoi în array[p..r]
. Trebuie să punem cea mai mică valoare din cele două subșiruri în array[p]
. Unde se află această valoare minimă? Deoarece subșirurile sunt sortate, cea mai mică valoare cu siguranță se află pe una dintre două poziții posibile: lowHalf[0]
sau highHalf[0]
. (Este posibil să existe aceeași valoare pe ambele poziții, iar în acest caz alegem una dintre ele.) Cu o singură comparație, putem decide pe care dintre lowHalf[0]
și highHalf[0]
să o copiem în array[p]
. În exemplul nostru, highHalf[0]
are valoarea mai mică. Haide să stabilim trei variabile cu care să indexăm subșirurile:i
indexează următorul element dinlowHalf
pe care nu l-am copiat încă înarray
. Inițial,i
este 0.j
indexează următorul element dinhighHalf
pe care nu l-am copiat încă înarray
. Inițial,j
este 0.k
indexează poziția dinarray
pe care urmează să copiem. Inițial,k
este egal cup
.
După ce copiem din
lowHalf
sau din highHalf
în array
, trebuie să îl incrementăm (să îl creștem cu 1) pe k
, astfel încât să copiem următorul cel mai mic element în următoarea poziție din array
. Trebuie să îl incrementăm și pe i
, dacă am copiat din lowHalf
, sau pe j
dacă am copiat din highHalf
. Iată subșirurile înainte și după ce primul element este copiat înapoi în array
:Am colorat cu gri
highHalf[0]
pentru a indica faptul că nu mai conține o valoare pe care o vom lua în considerare. Partea pe care încă nu am interclasat-o din subșirul highHalf
începe la poziția j
, care acum este 1. Valoarea din array[p]
nu mai este colorată cu gri, deoarece am copiat o valoare „reală” în elementul respectiv.Unde se află următoarea valoare ce trebuie copiată în
array
? Este fie primul element neadăugat din lowHalf
(lowHalf[0]
), fie primul element neadăugat din highHalf
(highHalf[1]
). Cu o comparație, aflăm că lowHalf[0]
este mai mic, așadar îl copiem în array[k]
și îi incrementăm pe k
și pe i
:În continuare, comparăm
lowHalf[1]
și highHalf[1]
și aflăm că trebuie să copiem highHalf[1]
în array[k]
. Apoi îi incrementăm pe k
și pe j
:Continuăm în acest fel, comparând întotdeauna
lowHalf[i]
și highHalf[j]
, copiind valoarea mai mică dintre cele două în array[k]
și incrementând fie i
, fie j
:În cele din urmă, fie întregul
lowHalf
, fie întregul highHalf
ajunge să fie copiat în array
. În acest exemplu, întregul highHalf
este copiat înaintea ultimelor elemente din lowHalf
. Finalizăm algoritmul prin copierea elementelor rămase în lowHalf
sau în highHalf
:Am spus că interclasarea a n elemente are timpul de execuție egal cu \Theta, left parenthesis, n, right parenthesis, așadar este liniar. Să vedem de ce este adevărat acest lucru. Am văzut că interclasarea are trei părți:
- Copiem fiecare element din
array[p..r]
înlowHalf
sau înhighHalf
. - Cât timp există elemente rămase în
lowHalf
și înhighHalf
, comparăm primele două elemente neadăugate și îl copiem pe cel mai mic înarray
. - Odată ce fie
lowHalf
, fiehighHalf
are toate elementele copiate înarray
, copiem toate elementele rămase în celălalt subșir temporar înarray
.
Câte linii de cod trebuie să executăm pentru fiecare dintre acești pași? Un număr constant per element. Fiecare element este copiat din
array
în lowHalf
sau în highHalf
o singură dată la pasul 1. Fiecare comparație de la pasul 2 se execută în timp constant, deoarece sunt comparate doar două elemente, iar un element „câștigă” o comparație cel mult o dată. Fiecare element este copiat înapoi în array
exact o singură dată la pașii 2 și 3. Din moment ce executăm fiecare linie de cod de un număr constat de ori pentru un element și presupunem că subșirul array[p..q]
conține n elemente, timpul de execuție pentru interclasare este, într-adevăr, \Theta, left parenthesis, n, right parenthesis.În următoarea provocare, vei implementa această operație de interclasare în timp liniar. Cu ajutorul următoarelor două provocări, vei fi implementat întregul algoritm de sortare prin interclasare.
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ă.