Clasa a 7-a Lecția 18: Divide et impera, mergesort, quicksort

Înregistrare video lecție

Tehnici de programare: divide et impera

Denumită și divide and conquer sau dezbină și stăpânește, este o tehnică cunoscută de mii de ani conducătorilor. Este o tehnică de cucerire sau menținere a puterii asupra unui grup care ar avea putere mai mare dacă s-ar uni. Ținând acel grup dezbinat, fiecare facțiune în parte are putere mică și poate fi cucerită, sau condusă. Tehnica a fost aplicată de Cezar, Napoleon, iar, mai recent, de către Britanici în Africa și de către Stalin în Rusia. Dintre tehnicile folosite în lumea reală putem menționa:

Ajutorarea și promovarea celor care cooperează cu puterea, pedepsirea celor ce nu cooperează.
Încurajarea cheltuielilor prostești, pentru a reduce capitalul disponibil organizării sau luptei.
Încurajarea divizării oamenilor pentru a preveni formarea alianțelor.
Încurajarea turnătorilor, cei care trâmbițează orice alianță posibil periculoasă.
Sădirea de neîncredere între oameni.

O parte din aceste tehnici se regăsesc și în țara noastră, precum și în majoritatea țărilor lumii, inclusiv cele dezvoltate. De exemplu, toate țările lumii folosesc un număr uriaș de taxe și impozite, fiecare din ele relativ mici. Când le însumăm constatăm că în jur de 90% din banii noștri se duc pe aceste taxe și impozite. Dacă ar exista o taxă unică de 90%, oamenii s-ar revolta. Astfel, tehnica de împărțire a unor taxe mari în mai multe taxe mici îi face pe oameni să nu le observe și să nu se revolte.

Pentru exemple clasice de folosire a acestei tehnici în lumea reală vizitați pagina de divide et impera a wikipediei.

Tehnica divide et impera (divide and conquer) în informatică

În informatică divide et impera constă în împărțirea problemei în subprobleme mai mici, nesuprapuse (o tehnică în care subproblemele sunt suprapuse este programarea dinamică). Fiecare din aceste subprobleme se rezolvă separat, mai ușor, deoarece sunt mai mici. Rezultatul final se obține din combinația rezultatelor subproblemelor.

Tehnica divide et impera simplă (decrease and conquer)

În următoarele exemple de divide et impera problema se reduce la o singură problemă, mai mică. Este un caz degenerat, în care implementarea poate fi iterativă (nu necesită recursivitate).

Algoritmul lui Euclid

Și acest bine cunoscut algoritm poate fi văzut ca un exemplu de divide et impera. El reduce problema de la cmmdc(a, b) la o problemă mai mică, cmmdc(b, a mod b). Complexitate: O(log min(a, b)).

Căutare binară

Precum știm, căutarea binară împarte vectorul original în două, apoi decide care din cele două jumătăți ar putea să conțină elementul căutat. Apoi rezolvă problema mai mică. Complexitate: O(log n).

Căutare punct fix

Se dă un vector sortat de n elemente întregi distincte. Să se găsească dacă există indicele i astfel încât v[i] == i. Găsiți un algoritm divide et impera care are complexitate O(log n).

Puzzle balanță

Avem 25 de bile care arată identic, una este ceva mai ușoară. Avem la dispoziție o balanță. Găsiți bila mai ușoară din trei cântăriri.

Selecția

Complexitate: pe medie O(n), în cel mai rău caz O(n²). Este necesară la problema AntiTir.

Probleme NerdArena

Următoarele probleme de la NerdArena sunt de divide et impera degenerat:

ZParcurgere
Tabela
AntiTir dată la Shumen 2012

Tehnica divide et impera propriu zisă

În următoarele exemple de divide et impera problema se reduce la două sau mai multe probleme mai mici. Implementarea este mult mai simplă dacă folosim recursivitate.

Puzzle pavare

Se dă o grilă de 2ⁿ x 2ⁿ pătrate din care lipsește un pătrat. Să se acopere cu piese formate din 3 pătrate aranjate în formă de litera L.

Problema pare destul de grea, nu? În realitate, odată ce încercăm să folosim divide et impera ea devine destul de ușoară. Cum putem împărți problema în probleme mai mici?

Să definim o problemă astfel:

P(n, gol) = pavează un pătrat de latură 2ⁿ care are un pătrățel lipsă (un gol).

O primă idee ar fi să încercăm să împărțim pătratul în patru pătrate de latură 2n-1 și să rezolvăm acele probleme. Avem, însă, o dificultate: doar unul din pătrate va avea un pătrățel lipsă. Celelalte trei vor fi pline. Ce ne facem?

Am putea încerca să eliminăm artificial câte un pătrățel din celelalte trei pătrate. Cum putem face acest lucru? Cu condiția ca cele trei pătrățele să fie în formă de L și să le acoperim cu o piesă elementară. Ei bine avem cum să alegem pătratele în acest fel: le vom selecta pe cele de la centru! Astfel vom obține subproblemele:

P(n, l, c) se descompune în:
   P(n-1, gol) (golul original)
   P(n-1, gol1)
   P(n-1, gol2)
   P(n-1, gol3)

Mergesort

Algoritmul mergesort, sau sortare prin interclasare, funcționează astfel:

Divide vectorul de sortat în două părți egale (sau aproape egale)
Reapelează mergesort pe acele părți
La revenire avem două jumătăți sortate, deci putem sorta vectorul interclasând cei doi vectori în timp liniar

Iată un algoritm:

mergesort( V[], i, j )
  mij = (i + j) / 2;
  daca i < mij
    mergesort( V[], i, mij )
  daca mij + 1 < j
    mergesort( V[], mij + 1, j )
  merge( V[], i, mij, j )

merge( V[], i, mij, j ) interclasează vectorii sortați V[i..mij] și V[mij+1..j].

Ce complexitate are mergesort?

Să calculăm numărul de operații, T(N), pentru a sorta un vector de N elemente:

T(N) = 2 · T(N/2) + N
T(N) = 2 · (2 · T(N/4) + N/2) + N
T(N) = 4 · T(N/4) + 2 · N
T(N) = 4 · (2 · T(N/8) + N/4) + 2 · N
T(N) = 8 · T(N/8) + 3 · N
...
T(N) = N · T(N/N) + log N · N
T(N) = N · T(1) + log N · N

Deoarece T(1) este O(1) rezultă o complexitate O(N + N log N) = O(N log N).

Câtă memorie suplimentară folosește algoritmul?

Pentru interclasarea clasică avem nevoie de un alt vector, deci O(N).

În concluzie avem complexitățile:

timp: O(n log n)
memorie suplimentară: O(n) (aceasta e problema principală a algoritmului).

Există variante ale algoritmului care folosesc mai puțină memorie (o idee evidentă este să folosim doar jumate din memorie deoarece în timpul interclasării putem suprascrie una din jumătăți).

Aplicație mergesort - inversiunile unei permutări

O problemă care apare uneori la concursuri este următoarea: se dă o permutare a numerelor de la 1 la N. Să se numere câte inversiuni are ea. O inversiune este o pereche de indici (i, j) astfel încât i < j și P[i] > P[j].

În linii mari, algoritmul este următorul:

Sortăm prima jumate a vectorului folosind un mergesort special, care ne returnează numărul de inversiuni din vectorul de sortat.
Sortăm a doua jumate a vectorului.
În acest moment știm inversiunile din cele două jumătăți - le adunăm.
Interclasăm cele două jumătăți. În timpul interclasării când selectăm un număr din prima jumătate știm că numerele deja selectate din jumătatea a doua sunt mai mici, deci putem aduna numărul lor la numărul total de inversiuni.

Quicksort

Algoritmul quicksort, sau sortare rapidă, inventat în 1959 de informaticianul britanic Tony Hoare, funcționează astfel:

Alege o poziție la întâmplare din vectorul de sortat. Vom denumi valoarea de la acea poziție pivot.
Rearanjează vectorul astfel încât în prima parte să avem elemente mai mici sau egale cu pivotul iar în a doua parte elemente mai mari sau egale cu pivotul. Vom denumi acest pas pivotare.
Reapelează quicksort pe acele două părți.

Din acest algoritm avem de lămurit pasul de pivotare. El este același ca la quickselect, prezentat într-o lecție anterioară. El procedează astfel:

Pornește cu doi indici, unul la începutul vectorului și unul la final de vector, să le spunem b și e.
Avansează indicele b până la primul element mai mare sau egal cu pivotul.
Devansează (merge înapoi) indicele e până la primul element mai mic sau egal cu pivotul.
Interschimbă elementele din vector de la pozițiile b și e.
Repetă până ce indicii se ating, b >= e.

Iată o implementare posibilă. Ea este implementarea originală a lui Hoare, transformată pentru a fi structurată:

void myqsort( int begin, int end ) {
  int aux, b = begin, e = end,
    pivot = v[(begin + end) / 2]; // poate fi orice pozitie intre begin si end - 1

  while (v[b] < pivot) // cauta primul element mai mare sau egal cu pivotul
    b++;

  while (v[e] > pivot) // cauta primul element mai mic sau egal cu pivotul
    e--;

  while( b < e ) { // daca indicii nu s-au atins
    aux = v[b];    // interschimba elementele la pozitiile b si e
    v[b] = v[e];
    v[e] = aux;
    
    do // cauta primul element mai mare sau egal cu pivotul
      b++;
    while (v[b] < pivot);

    do // cauta primul element mai mic sau egal cu pivotul
      e--;
    while (v[e] > pivot);
  }

  // acum [begin..e] sunt mai mici sau egale cu pivotul
  if ( begin < e )
    myqsort(begin, e);
  // si [e+1..end] sunt mai mari sau egale cu pivotul
  if ( e + 1 < end )
    myqsort(e + 1, end);
}

Ce complexitate are quicksort?

Deoarece pivotarea este liniară, calculele sunt similare cu cele de la mergesort. Avem două diferențe:

Procesarea liniară se face la început, înainte de recursie.
Împărțirea vectorului nu este neapărat în două părți egale, ceea ce duce la o complexitate O(N²) pe cazul cel mai rău.

Pentru cazul mediu, când împărțirea este în două părți aproximativ egale, rezultă aceeași complexitate O(N log N).

Câtă memorie suplimentară folosește algoritmul?

Memoria este cea necesară stivei. Ea va fi, deci, proporțională cu cel mai lung lanț de apeluri recursive imbricate. Pe cazul cel mai rău el este O(N), iar pe cazul mediu este O(log N).

Optimizare: putem reduce cazul cel mai rău astfel:

Observăm că al doilea apel recursiv este recursiv la coadă.
Precum știm, el nu va consuma memorie.
Putem reduce memoria stivei apelând mai întâi pentru partea mai mică ce rezultă după pivotare.

În acest fel chiar și în cazul cel mai rău memoria suplimentară necesară va fi O(log N).

În concluzie avem complexitățile:

timp: O(N log N)
memorie suplimentară: O(log N)

Atenție: deși putem selecta ca pivot orice element din vector, nu putem selecta ca pivot ultimul element. Aceasta ar duce la o buclă infinită.

Pivotarea Lomuto

În școli, de multe ori se predă un alt algoritm de pivotare, probabil deoarece este considerat mai simplu. Nu o vom discuta aici, deoarece este foarte ineficientă. Iată diferențele față de pivotarea Hoare:

Lomuto este ceva mai simplu de reținut și ceva mai scurtă.
Ambii algoritmi sunt cache friendly deoarece parcurg liniar vectorul.
Lomuto face de trei ori mai multe interschimburi.
Lomuto face O(N²) operații pe un vector sortat, Hoare doar O(N log N).
Lomuto face O(N²) operații pe un vector cu elemente egale, Hoare doar O(N log N).

Concluzie: Pivotarea Lomuto este un algoritm didactic, bun pentru înțelegerea pivotării, dar este contraindicat într-o implementare practică.

Randomizarea pivotului

Dacă alegem ca pivot prima poziție din vector, sau cea din mijloc, adversarul poate, studiind algoritmul, să găsească un vector special pe care implementarea noastră să intre pe cazul cel mai rău, O(N²). Putem lupta cu aceasta, alegând pivotul pe o poziție aleatoare din intervalul [begin..end-1].

Probleme quicksort

Atenție! Algoritmul este celebru pentru bug-urile pe care le putem introduce la implementare. Un semn mai mic transformat în mai mic sau egal poate duce la bucle infinite sau la un vector nesortat.

Soluție: pentru olimpiadă este bine să memorați algoritmul pe din-afară.

Ați putea spune hei, dar la olimpiadă pot folosi algorithms! Este opțiunea voastră, dar eu nu aș risca. Motivele împotriva folosirii funcției de sortare de bibliotecă:

Ea primește ca parametru o funcție de comparație. Apelul acelei funcții este lent, fiind vorba de accesul unui pointer pentru a obține adresa funcției, apoi de punerea pe stivă a parametrilor. Toate acestea se reduc la o comparație sau două în codul nostru.
Funcția de bibliotecă este o cutie neagră. Ea depinde de compilator și de biblioteca de funcții a acestuia. Ea este scrisă de alți oameni. Aveți mai multă încredere în cod scris de alții, care variază în funcție de calculatorul pe care se face evaluarea?
În mod uzual funcțiile de bibliotecă consumă mai multă memorie, iar uneori mult mai multă. De ce? Bună întrebare. Nu știu.
Algoritmul de mai sus are 23 de linii de cod efectiv. El este simplu și eficient și poate fi adaptat să sorteze orice tip de date, cu mici modificări. De ce am risca să apelăm o funcție de bibliotecă despre care nu știm nimic, când în 3 minute am scris acest cod?

Ziua regelui

Un rege organizează o petrecere mare de ziua lui. Petrecerea începe peste 24 de ore. Regele află că una din cele 1000 de sticle de vin pe care le va servi este otrăvită. Otrava acționează ciudat: omul care bea chiar și cea mai mică cantitate din această otravă nu are nici un simptom vreme de 24 de ore, apoi moare subit. Regele are sclavi la dispoziție pe care îi poate folosi. Lui nu îi pasă câți sclavi mor, dar îi pasă câți sclavi beau vin, deoarece un sclav care a băut vin nu poate fi folosit la treabă, ci trebuie izolat spre observare. Care este numărul minim de sclavi cu care regele poate afla sticla otrăvită?

Tema 18

Să se rezolve următoarele probleme (program C trimis la NerdArena):

Latin dată la cercul de informatică Vianu, gimnaziu 2013
Pav dată la Lot IS 2008
Forma dată la olimpiada pe sector 2012, clasa a 8-a

Tema opțională