Î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$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(n)$\Theta, left parenthesis, n, right parenthesis. Într-adevăr, vom vedea cum putem interclasa $n$n elemente în $\Theta(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-p+1$q, minus, p, plus, 1 elemente. Dar highHalf? Subșirul array[q+1..r] conține $r-q$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=0$p, equals, 0, $q=3$q, equals, 3, și $r=7$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:

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$n elemente are timpul de execuție egal cu $\Theta(n)$\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:

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$n elemente, timpul de execuție pentru interclasare este, într-adevăr, $\Theta(n)$\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.