Quicksort și pivotul
Quicksort este, în practică, una dintre cele mai rapide sortări. Alegi un element numit pivot, muți în stânga lui tot ce e mai mic și în dreapta tot ce e mai mare, apoi sortezi recursiv cele două părți. Totul se face pe loc, fără liste noi.
Partiționarea (schema Lomuto)
Lucrezi pe bucata a[st..dr]. Pivotul este ultimul element, a[dr] (alegere deterministă, ușor de urmărit). Indicele i arată unde va merge următorul element mai mic decât pivotul.
def partitie(a, st, dr):
pivot = a[dr]
i = st
for j in range(st, dr):
if a[j] < pivot:
a[i], a[j] = a[j], a[i] Scrie partitie(a, st, dr) (schema Lomuto, pivotul a[dr], returnează poziția finală a pivotului) și quicksort(a, st=0, dr=None), care sortează lista pe loc (nu returnează nimic). Nu folosi sort() sau sorted().
- În partitie: pivot = a[dr], i = st, mută elementele mai mici în față, apoi pune pivotul pe poziția i.
- În quicksort: dacă dr is None, dr = len(a) - 1; dacă st >= dr, te oprești; altfel partiționezi și sortezi cele două părți.
- Trebuie să apară: [1, 5, 7, 8, 9, 10], [1, 3, 3], [].
Restul explicațiilor, editorul și verificarea automată se deblochează cu Recursivitate, backtracking, sortare și căutare binară.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan