View source for Clasele 9-10 lecția 2 - 24 sep 2014

== Scop ==

Scopul practic al cercului de astăzi este să vă arate câteva sortări rapide aplicabile în situații speciale. Scopul principial este să vă dezvețe de a vă mai repezi la <tt>std::sort()</tt>. În principiu, noi suntem aici ca să învățăm să scriem algoritmi, nu ca să-i luăm de-a gata. Știu că mulți dintre voi alegeți să ignorați orice discuție de principiu, :-) așa încât iată câteva situații practice în care excesul de <tt>std::sort()</tt> dăunează grav timpilor de execuție.

Lecția este lungă. Probabil ne vom întinde pe două săptămâni.

== Reluarea unor probleme de cântărire ==

Reluăm o problemă propusă la lecția 1: ni se dau 9 bile identice ca formă, din care una este mai ușoară. Cum o putem depista din două cântăriri? Balanța are două talere și poate indica doar care este talerul mai greu (sau poate sta în echilibru). Soluția nu ar trebui să vă dea dureri de cap.

O problemă mai grea este: ni se dau 12 bile, din care una diferă ca greutate. Cum o putem depista din trei cântăriri?

''(căutăm împreună o soluție)''

Ce învățăm de aici? Dacă balanța poate da unul din trei răspunsuri la orice întrebare, atunci prin ''n'' întrebări putem diferenția cel mult 3<sup>''n''</sup> cazuri posibile. Dacă se dau 12 bile și una dintre ele este mai ușoară sau mai grea, înseamnă că spațiul soluțiilor conține 24 de posibilități. Fără să ne gândim deloc la detaliile problemei, știam că vor fi necesare cel puțin trei cântăriri. Apoi, putem testa rapid validitatea unei așezări pe talere, căci ea trebuie să lase, pentru oricare dintre rezultate, cel mult 3<sup>''c''</sup> cazuri posibile (unde ''c'' este numărul de cântăriri rămase).

Condiția este necesară, dar nu și suficientă. De exemplu, să considerăm aceeași problemă pentru 13 bile. Limita teoretică este întrunită, căci 13 ⨯ 2 = 26 ≤ 27. Dar există într-adevăr o soluție cu trei cântăriri?

''(căutăm împreună o soluție)''

Care este legătura cu sortarea? Dându-se un vector cu ''n'' elemente distincte, există ''n!'' permutări ale lui, dintre care una singură este sortată crescător. Dacă alegem să-l sortăm prin comparații binare, atunci, indiferent de algoritmul ales, după ''c'' căutări vom rămâne cu cel puțin <math>\frac{n!}{2^{c}}</math> posibilități de diferențiat. De aceea, orice sortare prin comparații consumă timp cel puțin

<math>O(\log_{2}{n!}) = O(n \log n)</math>

Există însă situații speciale când nu este nevoie să facem sortarea prin comparații.

== Cea mai rapidă sortare este cea pe care nu e nevoie să o faci ==

Există probleme care se rezolvă în <math>O(n)</math> fără sortare. În acest caz, o sortare în <math>O(n \log n)</math> vă strică complexitatea totală și este pierdere de vreme. Gândiți-vă bine înainte să trântiți un <tt>sort()</tt>!

* interclasarea a doi vectori sortați;
* găsirea elementului majoritar într-un vector cu ''n'' elemente;
* decizia dacă un vector cu ''n'' elemente este o permutare a mulțimii { 1, 2, ..., ''n'' };
* găsirea elementului lipsă într-un vector cu ''n - 1'' elemente distincte cu valori între 1 și ''n'';
* găsirea celui de-al ''k''-lea element ca valoare într-un vector nesortat

== Sortarea prin numărare ==

O menționăm rapid, căci nu poate fi omisă. Dacă valorile din vector sunt între 0 și ''k''-1, atunci îl putem sorta în <math>O(n)</math> folosind memorie suplimentară <math>O(k)</math>. Declarăm un vector auxiliar ''C'' unde ''C''[''i''] este numărul de apariții al lui ''i'' în vector.

''(scriem împreună rutina)''

Variante ale acestui algoritm se aplică pentru:

* valori între ''k''<sub>1</sub> și ''k''<sub>2</sub>, caz în care vectorul ''C'' trebuie decalat cu ''k''<sub>1</sub> poziții;
* valori de tip caracter sau de alt tip numărabil.

== Radix sort ==

Să considerăm că vectorul conține numere de trei cifre. Atunci îl putem sorta astfel:

* Definim un vector de 10 liste înlănțuite, L[0], L[1], ... L[9].
* Inițial toate listele sunt goale.
* Parcurgem vectorul și distribuim numerele în cele 10 liste potrivit cu '''ultima''' cifră. Inserarea se face neapărat la sfârșitul listei.
* Colectăm cele 10 liste, în ordine, suprascriind vectorul.
* Parcurgem vectorul și distribuim numerele în cele 10 liste potrivit cu cifra '''din mijloc.'''
* Colectăm cele 10 liste, în ordine, suprascriind vectorul.
* Parcurgem vectorul și distribuim numerele în cele 10 liste potrivit cu '''prima''' cifră.
* Colectăm cele 10 liste, în ordine, suprascriind vectorul.

=== Exemplu ===

Fie vectorul

<syntaxhighlight>v = { 19, 83, 47, 18, 55, 13, 23, 58 }</syntaxhighlight>

După prima distribuire,

<syntaxhighlight>  L[0] = NIL
  L[1] = NIL
  L[2] = NIL
  L[3] = 83, 13, 23
  L[4] = NIL
  L[5] = 55
  L[6] = NIL
  L[7] = 47
  L[8] = 18, 58
  L[9] = 19</syntaxhighlight>

Colectăm listele în ''v'':

<syntaxhighlight>
  v = { 83, 13, 23, 55, 47, 18, 58, 19 }
</syntaxhighlight>

După a doua distribuire (și ultima, în acest exemplu simplificat):

<syntaxhighlight>
  L[0] = NIL
  L[1] = 13, 18, 19
  L[2] = 23
  L[3] = NIL
  L[4] = 47
  L[5] = 55, 58
  L[6] = NIL
  L[7] = NIL
  L[8] = 83
  L[9] = NIL
</syntaxhighlight>

Colectăm listele în ''v'':

<syntaxhighlight>
  v = { 13, 18, 19, 23, 47, 55, 58, 83 }
</syntaxhighlight>

''(scriem împreună codul)''

Cifrele în baza 10 sunt bune pentru exemplificare, dar în practică folosim puteri ale lui 2 (256, 65.536 etc.). Ele permit extragerea unei „cifre” prin operații pe biți, nu prin operații modulo, care sunt mult mai lente.

Este important ca distribuirea și colectarea listelor să fie '''stabilă,''' adică să păstreze ordinea elementelor din aceeași listă. Nu putem strica la pasul 2 ceea ce am ordonat la pasul 1.

=== Complexitatea algoritmului naiv ===

Fie ''k'' baza în care operăm (10 în exemplul de mai sus) și fie ''d'' numărul maxim de cifre al numerelor din vector (așadar numerele au valori mai mici de <math>k^d</math>).

Timpul de rulare este <math>O(d(n + k))</math>, unde ''d'' este numărul maxim de cifre al numerelor din vector. Pentru numere întregi și baza ''k'' = 256, sunt necesare 4 iterații. Putem să alegem baza ''k'' = 65.536, dar trebuie să ținem minte că vom avea de iterat prin 65.536 de liste, ceea ce este nepractic pentru ''n'' mic.

Memoria suplimentară necesară constă din

* vectorul cu capetele de listă;
* un element din listă (întreg + pointer) pentru fiecare element din vector.

Așadar, algoritmul naiv este nepractic. El triplează memoria folosită și folosește pointeri, ceea ce duce la probleme de cache. Avem nevoie de o variantă '''in place,''' adică fără un vector suplimentar de ''n'' elemente.

=== Radix sort fără vector suplimentar ===

Reluăm exemplul pe două cifre, în baza zece.

<syntaxhighlight>
  v = { 19, 83, 47, 18, 55, 13, 23, 58 }
</syntaxhighlight>

Pornim cu cifra cea mai semnificativă. Facem o trecere prin vector și numărăm de câte ori apare fiecare cifră.

<syntaxhighlight>
  cate = { 0, 3, 1, 0, 1, 2, 0, 0, 1, 0 }
</syntaxhighlight>

Precalculăm pozițiile din vector pe care le vor ocupa numerele cu prima cifră 0, 1, ... Reținem aceste intervale închise la stânga, deschise la dreapta. De exemplu, numerele care încep cu 5 vor ocupa pozițiile 5 și 6 în vector, deci intervalul [5, 7).

<syntaxhighlight>
  prima  = { 0, 0, 3, 4, 4, 5, 7, 7, 7, 8 }
  ultima = { 0, 3, 4, 4, 5, 7, 7, 7, 8, 8 }
</syntaxhighlight>

(Puteți verifica corectitudinea vectorilor ''prima'' și ''ultima'' examinând vectorul sortat { 13, 18, 19, 23, 47, 55, 58, 83 }).

Dorim acum să mutăm fiecare număr în intervalul lui corect, conform primei cifre. Deoarece nu dorim să folosim vectori suplimentari, vom face interschimbări astfel:

* Pentru fiecare cifră de la 0 la 9, menținem un pointer la primul element încă neexaminat.
** Inițial, acești pointeri coincid exact cu vectorul ''prima''.
** În practică, vom refolosi chiar vectorul ''prima'', incrementând diverse valori prin el pe măsură ce examinăm elemente.
** La final, vectorul ''prima'' va coincide cu ''ultima''.
* Parcurgem toate cifrele de la 0 la 9.
* Pentru fiecare cifră ''c'' parcurgem intervalul din vector de la ''prima[c]'' la ''ultima[c]''. Dorim să aducem pe fiecare poziție un număr care începe cu cifra ''c''.
* Pentru fiecare număr întâlnit care nu începe cu cifra ''c'', îi calculăm ''bucketul'' corect și îl interschimbăm cu următorul element din acel ''bucket''.
** La nevoie, repetăm această operație până când pe poziția curentă ajunge un număr care începe cu cifra ''c''.

Exemplificăm un singur pas al acestui algoritm. Pentru cifra 0 nu avem nimic de făcut, căci deja prima[0] = ultima[0]. Pentru cifra 1, dorim să aducem pe pozițiile 0, 1 și 2 numere care încep cu 1. Pe poziția 0 îl avem deja pe 19. Pe poziția 1 îl avem pe 83. 83 ar trebui să fie în ''bucketul'' 8, deci îl schimbăm cu elementul 58:

<syntaxhighlight>
  v = { 19, '''58,''' 47, 18, 55, 13, 23, '''83''' }
  prima  = { 0, 0, 3, 4, 4, 5, 7, 7, '''8,''' 8 }
  ultima = { 0, 3, 4, 4, 5, 7, 7, 7, 8, 8 }
</syntaxhighlight>

58 ar trebui să fie în ''bucketul'' 5, deci îl schimbăm cu elementul 13. Acum 13 este un element acceptabil pe poziția curentă, deci incrementăm pointerul.

<syntaxhighlight>
  v = { 19, '''13,''' 47, 18, 55, '''58,''' 23, 83 }
  prima  = { 0, '''1,''' 3, 4, 4, '''6,''' 7, 7, 8, 8 }
  ultima = { 0, 3, 4, 4, 5, 7, 7, 7, 8, 8 }
</syntaxhighlight>

Observăm că acest algoritm nu este stabil. Dacă l-am aplica începând cu ultima cifră, ca pe radix sort-ul clasic, o iterație ar putea inversa elemente sortate de iterațiile anterioare. Pe de altă parte, dacă îl aplicăm în ordinea descrescătoare a poziției, atunci pasul 2 va strica ce a ordonat pasul 1. De aceea, vom începe cu cifra cea mai semnificativă, dar vom sorta recursiv cele 10 intervale obținute, ținând cont de a doua cifră (acest algoritm are deci elemente comune și cu quicksort).

O altă observație importantă este că, pentru porțiuni mici din vector, nu mai rentează să reapelăm recursiv radix sort. Acesta iterează mereu prin vectorul de cifre, care în practică are 256 de elemente. Pentru vectori mai mici de 40-60-100 de elemente, recurgem la sortarea prin selecție.

=== Măsurători ===

Am comparat <tt>std::sort()</tt> cu radix sort clasic și cu radix sort fără vector suplimentar. Am variat următorii parametri:

* lui N i-am dat valorile 1.000.000 și 10.000.000
* vectorii au fost generați prin trei metode: aleator, sortați crescător, sortați descrescător

{|class="wikitable"
! N = 1.000.000 || std::sort || radix1 || radix2
|-
| vector aleator || 122 ms || 215 ms || 67 ms
|-
| vector crescător || 23 ms || 218 ms || 51 ms
|-
| vector descrescător || 168 ms || 215 ms || 51 ms
|}

{|class="wikitable"
! N = 10.000.000 || std::sort || radix1 || radix2
|-
| vector aleator || 1.395 ms || 2.810 ms || 457 ms
|-
| vector crescător || 310 ms || 2.820 ms || 268 ms
|-
| vector descrescător || 1.979 ms || 2.810 ms || 333 ms
|}

Concluzia? Radix sort are limitări. Nu se pretează la numere negative, la numere reale etc. Dar, când merge, merge '''mult''' mai rapid decât <tt>std::sort</tt>. Cazul de interes practic pentru olimpiadă este N = 1.000.000, unde radix sort economisește zeci de milisecunde.

=== Surse ===

* [[Media:stdsort.cpp]]
* [[Media:radix.cpp]]
* [[Media:radix2.cpp]]

== Quicksort ternar pentru șiruri de caractere ==

Cum reprezentăm și cum sortăm șiruri de caractere? Iată trei versiuni de program care fac același lucru: generează 1.000.000 de șiruri de caractere, cu lungimi aleatoare între 20 și 50, conținând caractere aleatoare între ''a'' și ''d'', apoi între ''a'' și ''z''. Apoi sortează aceste șiruri de caractere.

# [[media:stl-sort.cpp|Versiunea 1]] reprezintă șirurile folosind <tt>std::string</tt> și le sortează cu <tt>std::sort()</tt>.
# [[media:stl-sort-charp.cpp|Versiunea 2]] reprezintă șirurile folosind <tt>char*</tt> și le sortează cu <tt>std::sort()</tt>. Rutina de comparare este un wrapper peste <tt>strcmp()</tt>.
# [[media:ternary-qsort.cpp|Versiunea 3]] reprezintă șirurile folosind <tt>char*</tt> și le sortează cu un quicksort ternar (detalii mai jos).

Rezultate:

{|class="wikitable"
! versiune || timp (caractere a-d) || timp (caractere a-z)
|-
| std::string + std::sort() || 1.902 ms || 1.784 ms
|-
| char* + std::sort() + strcmp || 967 ms || 916 ms
|-
| char* + quicksort ternar || 404 ms || 386 ms
|}

Rezultatele vorbesc de la sine. În primul rând, implementarea cu <tt>string</tt> în loc de <tt>char*</tt> este '''dezastruoasă.''' Când procesarea de șiruri este principala sursă a complexității, feriți-vă de <tt>string</tt>! În al doilea rând, pentru sortarea unui număr mare de șiruri, folosiți quicksort ternar.

=== Algoritmul de quicksort ternar ===

Ce este quicksort ternar? El încearcă să evite un mare dezavantaj al sortărilor de stringuri bazate exclusiv pe comparații. Spre deosebire de comparările de întregi, care se fac în O(1), comparările de stringuri se fac în O(|s|), unde |s| este lungimea șirurilor. Dorim deci să aflăm informații parțiale, sortând prefixe tot mai lungi ale șirurilor.

Concret, pentru a sorta ''n'' stringuri, vom alege un caracter oarecare (echivalent pivotului) și vom împărți vectorul de stringuri în 3 grupe, de la stânga la dreapta: cele al căror prim caracter este mai mic, respectiv egal, respectiv mai mare decât caracterul oarecare. Apoi vom sorta recursiv cele trei bucăți astfel:

* în prima grupă, reapelăm quicksortul ternar, alegând alt prim caracter
* la fel și în a treia grupă
* în grupa a doua, unde toate stringurile încep cu același caracter, reapelăm quicksortul ternar comparând poziția a doua a șirurilor

Observăm că quicksort-ul ternar aduce un pic a radix sort. Algoritmul a fost inventat de Sedgewick.

Codul rezultat este:

<syntaxhighlight lang="c">
void tsort(char **s, int lo, int hi, int pos) {
  if (lo >= hi) {
    return;
  }

  int curr = lo, left = lo, right = hi;
  char mid = (s[lo][pos] + s[hi][pos]) / 2;
  char *tmp;

  // invariant: la fiecare moment,
  // * s[lo ... left - 1] conține elemente unde al pos-lea caracter este mai mic decât mid
  // * s[left ... curr - 1] conține elemente unde al pos-lea caracter este egal cu mid
  // * s[curr] este șirul curent, din care evaluăm al pos-lea caracter
  // * s[curr + 1 ... right] conține elemente încă neevaluate
  // * s[right + 1 ... hi] conține elemente unde al pos-lea caracter este mai mare decât mid
  while (curr <= right) {
    char c = s[curr][pos];
    if (c < mid) {
      tmp = s[curr];
      s[curr] = s[left];
      s[left] = tmp;
      left++;
      curr++;
    } else if (c > mid)  {
      tmp = s[curr];
      s[curr] = s[right];
      s[right] = tmp;
      right--;
    }  else {
      curr++;
    }
  }

  tsort(s, lo, left - 1, pos);
  if (s[left][pos] != '\0' ) {
    tsort(s, left, right, pos + 1);
  }
  tsort(s, right + 1, hi, pos);
}

int main(void) {
  char* s[n];
  ...
  tsort(s, 0, N - 1, 0);
  ...
}
</syntaxhighlight>

== Concluzie ==

''Dacă tot ce ai este un ciocan, totul în jurul tău arată ca un cui.'' ([http://en.wiktionary.org/wiki/if_all_you_have_is_a_hammer,_everything_looks_like_a_nail originea zicalei])

== Temă ==

* [http://varena.ro/runda/tema01-juniori-2014-2015 Tema 1 juniori]