Sortare

Presupunem ca avem o permutare de lungime n si pozitiile An, Bn si Cn. Vom considera doua cazuri:

  1. An ≠ Bn ≠ Cn
    In cazul in care cei trei indici sunt diferiti este evident ca nu poate aparea ca pivot numarele 1 sau n, deoarece nu exista numere mai mici, respectiv mai mari decat ele. In schimb, putem construi sirul astfel sa apara ca pivot orice numar de la 2 la n-1. Deoarece vrem ca adancimea sa fie maxima, trebuie ca una din cele doua bucati care se obtin dupa partititonare sa fie cat mai mare. Asadar, are rost sa punem ca pivot doar 2 sau n-1, reducand rezolvarea pentru lungimea n la rezolvarea lungimii 1 si lungimii n-2.
  2. An = Bn sau An ≠ Cn sau An ≠ Bn
    In cazul in care cel putin doi din indici sunt egali putem aplica un rationament ca cel de mai sus, doar ca de data asta putem pune ca pivot si numerele 1 si n. Astfel, rezolvarea pentru lungime n se reduce la rezolvarea lungimii n-1.

Pe baza acestor doua observatii putem face o rezolvare recursiva care alege pivotul in mod greedy in functie de cele doua cazuri. Complexitatea rezolvarii este O(N2).