Recursivitate exemplificată prin sortarea rapidă (quicksort)
Să analizăm utilizarea recursivității pe exemplul algoritmului de sortare rapidă. Definim următorul cod:
#include <iostream>
void sort(int[], size_t, size_t);
void swap(int[], size_t, size_t);
int main()
{
int nums[] {3, 0, 6, -2, -6, 11, 3};
sort(nums, 0, std::size(nums)-1);
for(auto num: nums)
{
std::cout << num << "\t";
}
std::cout << std::endl;
}
void sort(int numbers[], size_t start, size_t end)
{
// indicele de început trebuie să fie mai mic decât cel de sfârșit pentru un array cu 2 sau mai mulți elemente
if (start >= end)
return;
// verificăm toți elementele în raport cu cel de la indexul start
size_t current {start};
for (size_t i {start + 1}; i <= end; i++)
{
// dacă elementul i este mai mic decât cel inițial
if (numbers[i] < numbers[start])
{
swap(numbers, ++current, i); // îl schimbăm cu cel din stânga
}
}
swap(numbers, start, current); // schimbăm elementul inițial cu ultimul element mai mic găsit
if (current > start)
{
sort(numbers, start, current - 1); // sortăm elementele din stânga
}
if (end > current + 1)
{
sort(numbers, current + 1, end); // sortăm elementele din dreapta
}
}
void swap(int numbers[], size_t first, size_t second)
{
auto temp{numbers[first]};
numbers[first] = numbers[second];
numbers[second] = temp;
}Pentru sortarea vectorului este definită funcția sort, care primește trei parametri: vectorul de sortat, indicele de început și cel de sfârșit al secțiunii de sortat:
void sort(int numbers[], size_t start, size_t end)La primul apel al funcției, se presupune că indicele start este 0, iar end este indicele ultimului element al vectorului.
La început, verificăm dimensiunea secțiunii de sortat:
if (start >= end)
return;Dacă start >= end, înseamnă că secțiunea conține 0 sau 1 element, deci este deja sortată.
La fiecare apel al funcției sort(), secvența curentă este împărțită în două secvențe mai mici, pentru fiecare dintre care se apelează recursiv sort(). Astfel, în final vom obține secvențe care conțin un singur element.
Apoi setăm indexul elementului curent:
size_t current {start};În continuare, în ciclu, comparăm acest element cu toate celelalte care urmează după start:
for (size_t i {start + 1}; i <= end; i++)
{
// dacă elementul i este mai mic decât cel inițial
if (numbers[i] < numbers[start])
{
swap(numbers, ++current, i); // îl schimbăm cu elementul din stânga
}
}Dacă elementul i este mai mic decât cel ales (elementul de la start), îl schimbăm cu elementul care urmează după start. Astfel, toate elementele mai mici decât cel ales sunt mutate înaintea celor mai mari sau egale cu el.
Când ciclul se termină, variabila current conține indexul ultimului element mai mic decât cel ales. Apoi, schimbăm aceste două elemente:
swap(numbers, start, current);Astfel, elementul față de care s-au făcut comparațiile ajunge pe poziția corectă (indexul current) și se află după toate elementele mai mici decât el.
La final, sortăm recursiv cele două sub-secvențe din stânga și din dreapta elementului de la current, apelând sort() pentru fiecare subset:
if (current > start)
{
sort(numbers, start, current - 1); // sortăm partea stângă
}
if (end > current + 1)
{
sort(numbers, current + 1, end); // sortăm partea dreaptă
}De exemplu, la prima execuție valorile inițiale vor fi:
start = 0
end = 6
current = 0Ciclul va face 7 iterații, în timpul cărora vectorul se va modifica astfel:
- după iterația 1: 3 0 6 -2 -6 11 3
- după iterația 2: 3 0 6 -2 -6 11 3
- după iterația 3: 3 0 -2 6 -6 11 3
- după iterația 4: 3 0 -2 -6 6 11 3
- după iterația 5: 3 0 -2 -6 6 11 3
- după iterația 6: 3 0 -2 -6 6 11 3
- după iterația 7: 3 0 -2 -6 6 11 3
Variabila current va fi egală cu 3, adică au fost găsite trei elemente mai mici decât cel ales (3). Apoi schimbăm "start" cu "current":
-6 0 -2 3 6 11 3Apoi împărțim în două sub-secvențe: la stânga de current:
-6 0 -2și la dreapta de current:
6 11 3Și pentru fiecare dintre aceste sub-secvențe apelăm separat funcția sort().
