Algoritmi de Sortare
Algoritmi de Sortare¶
De ce contează sortarea?¶
Sortarea este probabil cea mai studiată problemă din informatică. Un array sortat deschide ușa către o multitudine de operații eficiente: căutare binară în $O(\log n)$, detectarea duplicatelor în $O(n)$, găsirea medianei în $O(1)$, merge eficient al mai multor secvențe. Mulți algoritmi avansați presupun input sortat ca prim pas.
Algoritmi Elementari: $O(n^2)$¶
Insertion Sort¶
Ideea: parcurgem array-ul de la stânga la dreapta, și la fiecare pas inserăm elementul curent în poziția corectă în porțiunea deja sortată.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
# Deplasăm elementele mai mari cu o poziție la dreapta
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
Complexitate: $O(n^2)$ worst/average, dar $O(n)$ pe un array aproape sortat — de aceea este folosit ca finalizare în algoritmi hibriți (Timsort).
Stabilitate: Da — elementele egale își păstrează ordinea relativă.
Selection Sort¶
Ideea: la fiecare pas, găsim minimul din porțiunea nesortată și îl punem pe poziția corectă.
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
Complexitate: $O(n^2)$ mereu — nu are best case mai bun. Avantaj: face exact $n-1$ swap-uri, util dacă operația de scriere e costisitoare.
Bubble Sort¶
Ideea: parcurgem array-ul repetat, comparăm perechi adiacente și le interschimbăm dacă sunt în ordine greșită. Repetăm până nu mai avem swap-uri.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break # optimizare: deja sortat
return arr
Complexitate: $O(n^2)$ worst/average, $O(n)$ best case (cu optimizarea swapped).
Când folosim $O(n^2)$? Pe array-uri mici ($n < 20$) — overhead-ul algoritmilor avansați depășește câștigul. De aceea Timsort (Python) și Introsort (C++) comută la Insertion Sort sub un prag.
Merge Sort¶
Paradigma: Divide și Cucerește.
- Divide: împarte array-ul în două jumătăți
- Cucerește: sortează recursiv fiecare jumătate
- Combină: interclasează cele două jumătăți sortate
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
"""
Interclasare — O(n).
Comparăm primele elemente din fiecare jumătate,
alegem pe cel mai mic, avansăm pointer-ul corespunzător.
"""
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= pentru stabilitate
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# Adăugăm elementele rămase
result.extend(left[i:])
result.extend(right[j:])
return result
Analiză cu Teorema Master: $T(n) = 2T(n/2) + O(n)$
$a = 2, b = 2, c = 1 \implies \log_2 2 = 1 = c$ → Cazul 2: $T(n) = O(n \log n)$
Proprietăți:
- Timp: $O(n \log n)$ garantat (best = average = worst)
- Spațiu: $O(n)$ — necesită array auxiliar
- Stabil: da
- Ideal pentru: sortare pe disc (external sort), linked lists
Quick Sort¶
Paradigma: Divide și Cucerește (dar diferit de Merge Sort).
- Alege un element pivot
- Partiționează: mută elementele $\leq$ pivot la stânga, $>$ pivot la dreapta
- Sortează recursiv cele două partiții
def quick_sort(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
pivot_idx = partition(arr, low, high)
quick_sort(arr, low, pivot_idx - 1)
quick_sort(arr, pivot_idx + 1, high)
return arr
def partition(arr, low, high):
"""
Partiționare Lomuto: pivotul e ultimul element.
Variabila i marchează granița — totul la stânga lui i
este ≤ pivot.
"""
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
Alegerea pivotului¶
Pivotul este totul în Quick Sort. Un pivot prost (cel mai mic sau cel mai mare element) face partiții dezechilibrate, ducând la $O(n^2)$.
import random
def partition_random(arr, low, high):
"""Pivot aleator — O(n log n) cu probabilitate mare"""
rand_idx = random.randint(low, high)
arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
return partition(arr, low, high)
def median_of_three(arr, low, high):
"""Mediana din first, middle, last — evită worst case pe date sortate"""
mid = (low + high) // 2
if arr[low] > arr[mid]:
arr[low], arr[mid] = arr[mid], arr[low]
if arr[low] > arr[high]:
arr[low], arr[high] = arr[high], arr[low]
if arr[mid] > arr[high]:
arr[mid], arr[high] = arr[high], arr[mid]
# Mediana e acum la mid; o punem la high-1 ca pivot
arr[mid], arr[high] = arr[high], arr[mid]
return partition(arr, low, high)
Partiționare Hoare (mai eficientă)¶
def partition_hoare(arr, low, high):
"""
Doi pointeri vin din direcții opuse.
~3x mai puține swap-uri decât Lomuto în practică.
"""
pivot = arr[(low + high) // 2]
i, j = low - 1, high + 1
while True:
i += 1
while arr[i] < pivot:
i += 1
j -= 1
while arr[j] > pivot:
j -= 1
if i >= j:
return j
arr[i], arr[j] = arr[j], arr[i]
Proprietăți Quick Sort:
- Timp: $O(n \log n)$ average, $O(n^2)$ worst case
- Spațiu: $O(\log n)$ (stiva de recursivitate)
- Nu e stabil
- De ce e cel mai rapid în practică? Excelent cache locality (operează in-place), factor constant mic, pivot random elimină worst case
Counting Sort: Sub $O(n \log n)$?¶
Algoritmii bazați pe comparații au o limită inferioară de $\Omega(n \log n)$. Dar dacă știm că valorile sunt în intervalul $[0, k)$, putem sorta în $O(n + k)$ fără comparații:
def counting_sort(arr, max_val=None):
"""
Sortare prin numărare — O(n + k).
Funcționează doar pe numere întregi non-negative.
"""
if not arr:
return arr
if max_val is None:
max_val = max(arr)
# Numărăm aparițiile
count = [0] * (max_val + 1)
for x in arr:
count[x] += 1
# Reconstruim array-ul sortat
result = []
for val in range(max_val + 1):
result.extend([val] * count[val])
return result
Versiunea stabilă (necesară pentru Radix Sort)¶
def counting_sort_stable(arr, key=lambda x: x, max_val=None):
"""Versiune stabilă — păstrează ordinea relativă a elementelor egale"""
if not arr:
return arr
if max_val is None:
max_val = max(key(x) for x in arr)
count = [0] * (max_val + 1)
for x in arr:
count[key(x)] += 1
# Prefix sums — count[i] = câte elemente au key ≤ i
for i in range(1, len(count)):
count[i] += count[i - 1]
# Construim rezultatul de la dreapta la stânga (pentru stabilitate)
result = [None] * len(arr)
for x in reversed(arr):
k = key(x)
count[k] -= 1
result[count[k]] = x
return result
Radix Sort¶
Sortează numere cifră cu cifră, folosind un sort stabil (Counting Sort) ca subrutină:
def radix_sort(arr):
"""
Sortare pe cifre — O(d × (n + k))
unde d = nr. de cifre, k = baza (10 pentru zecimal).
"""
if not arr:
return arr
max_val = max(arr)
exp = 1
while max_val // exp > 0:
arr = counting_sort_stable(arr, key=lambda x: (x // exp) % 10, max_val=9)
exp *= 10
return arr
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]
Limita inferioară: $\Omega(n \log n)$¶
Orice algoritm de sortare bazat pe comparații necesită cel puțin $\Omega(n \log n)$ comparații în worst case.
Demonstrație (schiță): Un array de $n$ elemente are $n!$ permutări posibile. Algoritmul poate fi modelat ca un arbore de decizie binar cu $n!$ frunze. Înălțimea minimă a unui arbore binar cu $n!$ frunze este:
$$h \geq \log_2(n!) = \Omega(n \log n) \quad \text{(formula lui Stirling)}$$
Counting Sort și Radix Sort ocolesc această limită deoarece nu folosesc comparații — exploatează structura datelor (valori întregi într-un interval known).
Comparație Completă¶
| Algoritm | Best | Average | Worst | Spațiu | Stabil | Observații |
|---|---|---|---|---|---|---|
| Insertion | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | ✅ | Excelent pe date aproape sortate |
| Selection | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | ❌ | Puține swap-uri |
| Bubble | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | ✅ | Rar folosit în practică |
| Merge Sort | $O(n\log n)$ | $O(n\log n)$ | $O(n\log n)$ | $O(n)$ | ✅ | Garantat, ideal pt external sort |
| Quick Sort | $O(n\log n)$ | $O(n\log n)$ | $O(n^2)$ | $O(\log n)$ | ❌ | Cel mai rapid în practică |
| Counting | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | $O(k)$ | ✅ | Doar numere întregi, interval mic |
| Radix | $O(d(n+k))$ | $O(d(n+k))$ | $O(d(n+k))$ | $O(n+k)$ | ✅ | $d$ = nr. cifre |
Ce folosesc limbajele în practică?¶
-
Python (
sorted(),list.sort()) — Timsort: un hibrid Merge Sort + Insertion Sort. Detectează „runs" (porțiuni deja sortate) și le interclasează. $O(n \log n)$ worst case, $O(n)$ pe date parțial sortate. -
C++ (
std::sort) — Introsort: Quick Sort cu pivot median-of-three, comută la Heap Sort dacă recurența devine prea adâncă, și la Insertion Sort sub un prag (~16 elemente). $O(n \log n)$ garantat. -
Java (
Arrays.sort) — Dual-Pivot Quick Sort pentru primitive, Timsort pentru obiecte.
Exerciții¶
-
Implementați Merge Sort pe o listă înlănțuită (aici Merge Sort are avantaj real față de Quick Sort — de ce?)
-
Quick Select: modificați Quick Sort pentru a găsi al $k$-lea cel mai mic element în $O(n)$ average:
python def quick_select(arr, k): # Hint: nu trebuie să sortați ambele partiții pass -
Dați un exemplu de array care face Quick Sort (cu pivot = ultimul element) să ruleze în $O(n^2)$
-
Implementați sortare stabilă pentru un array de obiecte, sortând după un câmp — demonstrați că Merge Sort păstrează ordinea relativă a elementelor egale, dar Quick Sort nu