Quick sort
Ultimo aggiornamento
Il quicksort è un algoritmo divide et impera che ordina attorno a un "pivot". Sceglie un elemento pivot, poi partiziona l'array in modo che tutto ciò che è più piccolo venga prima e tutto ciò che è più grande venga dopo, fissando così il pivot nella sua posizione ordinata finale. Poi procede ricorsivamente sulle partizioni sinistra e destra. Questa visualizzazione usa lo schema di Lomuto con l'ultimo elemento come pivot. Premi play per vedere il partizionamento e il posizionamento del pivot.
In pratica il quicksort è di solito l'ordinamento generico più veloce, grazie a un buon uso della cache e al partizionamento in loco, con una media di O(n log n). Il suo caso peggiore è O(n²) (ad es. un array già ordinato con una cattiva scelta del pivot), che buone strategie di scelta del pivot come la mediana di tre o la randomizzazione evitano.
Complessità temporale e spaziale
| Caso | Complessità | Note |
|---|---|---|
| Caso migliore | O(n log n) | Partizioni bilanciate |
| Caso medio | O(n log n) | Ordine casuale |
| Caso peggiore | O(n²) | Pivot sempre sbilanciati |
| Spazio | O(log n) | Stack della ricorsione (partizione in loco) |
| Stabile | No | Gli scambi della partizione riordinano gli elementi uguali |
Passo dopo passo
| Passo | Cosa succede |
|---|---|
| 1 | Scegli un pivot (qui, l'ultimo elemento dell'intervallo). |
| 2 | Partiziona: sposta tutti gli elementi più piccoli del pivot alla sua sinistra. |
| 3 | Scambia il pivot sul confine: ora è nella sua posizione finale. |
| 4 | Applica ricorsivamente il quicksort alla partizione sinistra. |
| 5 | Applica ricorsivamente il quicksort alla partizione destra. |
Esempio svolto
Ordinamento di [5, 2, 4, 1] con lo schema di Lomuto (ultimo elemento come pivot):
| Passata | Array | Azione |
|---|---|---|
| Inizio | [5, 2, 4, 1] | Partiziona l'intero intervallo; il pivot è 1 (ultimo elemento). |
| 1 | [1, 2, 4, 5] | Niente è più piccolo di 1, quindi scambia 1 all'indice 0; il pivot 1 ora è definitivo. Procedi ricorsivamente a destra su [2, 4, 5]. |
| 2 | [1, 2, 4, 5] | Partiziona [2, 4, 5] con pivot 5; sia 2 sia 4 sono più piccoli, quindi 5 resta in fondo ed è definitivo. Procedi ricorsivamente a sinistra su [2, 4]. |
| 3 | [1, 2, 4, 5] | Partiziona [2, 4] con pivot 4; 2 è più piccolo, quindi 4 resta dov'è ed è definitivo. 2 è un solo elemento, quindi è già ordinato. |
| Fine | [1, 2, 4, 5] | Ogni pivot è fissato al suo posto; l'array è ordinato. |
Quando usare il quicksort
| Usalo quando | Evitalo quando |
|---|---|
| Ti serve un ordinamento in memoria veloce e generico con fattori costanti piccoli. | Ti serve un tempo O(n log n) garantito nel caso peggiore (usa heap sort o merge sort). |
La memoria è poca: il partizionamento è in loco e richiede solo O(log n) di spazio sullo stack. | Ti serve un ordinamento stabile che preservi l'ordine delle chiavi uguali. |
| I dati sono in ordine casuale o sconosciuto e usi un pivot casuale o la mediana di tre. | L'input è già ordinato o quasi e il pivot è fisso, cosa che fa scattare O(n²). |
| Conta una buona località della cache, dato che il quicksort accede alla memoria in modo sequenziale. | Stai ordinando una lista concatenata, dove il merge sort evita l'accesso casuale su cui si basa il quicksort. |
Codice Quick Sort
Un'implementazione di Quick Sort pulita ed eseguibile in Python, JavaScript, Java, C++, C, Pseudocode. Scegli un linguaggio, copia il codice o aprilo già caricato nel Playground di Coddy.
Codice Quick Sort in Python
Python
1def quick_sort(a, low=0, high=None):2 if high is None:3 high = len(a) - 14 if low < high:5 p = partition(a, low, high)6 quick_sort(a, low, p - 1)7 quick_sort(a, p + 1, high)8 return a9
10
11def partition(a, low, high):12 # Lomuto partition: everything < pivot moves left of it13 pivot = a[high]14 i = low15 for j in range(low, high):16 if a[j] < pivot:17 a[i], a[j] = a[j], a[i]18 i += 119 a[i], a[high] = a[high], a[i]20 return i21
22
23nums = [10, 7, 8, 9, 1, 5]24print("Before:", nums)25quick_sort(nums)26print("After: ", nums)Codice Quick Sort in JavaScript
JavaScript
1function quickSort(a, lo = 0, hi = a.length - 1) {2 if (lo >= hi) return a;3 const p = partition(a, lo, hi);4 quickSort(a, lo, p - 1);5 quickSort(a, p + 1, hi);6 return a;7}8
9// Lomuto partition: last element is the pivot10function partition(a, lo, hi) {11 const pivot = a[hi];12 let i = lo;13 for (let j = lo; j < hi; j++) {14 if (a[j] < pivot) {15 [a[i], a[j]] = [a[j], a[i]];16 i++;17 }18 }19 [a[i], a[hi]] = [a[hi], a[i]];20 return i;21}22
23const data = [5, 2, 9, 1, 7, 3];24console.log("Before:", data);25console.log("Sorted:", quickSort([...data]));Codice Quick Sort in Java
Java
1import java.util.Arrays;2
3public class Main {4 static void quickSort(int[] arr, int low, int high) {5 if (low >= high) return;6 int p = partition(arr, low, high);7 quickSort(arr, low, p - 1);8 quickSort(arr, p + 1, high);9 }10
11 // Lomuto partition: last element is the pivot12 static int partition(int[] arr, int low, int high) {13 int pivot = arr[high];14 int i = low - 1;15 for (int j = low; j < high; j++) {16 if (arr[j] < pivot) swap(arr, ++i, j);17 }18 swap(arr, i + 1, high);19 return i + 1;20 }21
22 static void swap(int[] arr, int a, int b) {23 int tmp = arr[a];24 arr[a] = arr[b];25 arr[b] = tmp;26 }27
28 public static void main(String[] args) {29 int[] arr = {10, 7, 8, 9, 1, 5};30 System.out.println("Before: " + Arrays.toString(arr));31 quickSort(arr, 0, arr.length - 1);32 System.out.println("After: " + Arrays.toString(arr));33 }34}Codice Quick Sort in C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10// Lomuto partition: place the pivot in its final position11int partition(std::vector<int>& a, int lo, int hi) {12 int pivot = a[hi];13 int i = lo;14 for (int j = lo; j < hi; ++j) {15 if (a[j] < pivot) std::swap(a[i++], a[j]);16 }17 std::swap(a[i], a[hi]);18 return i;19}20
21void quickSort(std::vector<int>& a, int lo, int hi) {22 if (lo >= hi) return;23 int p = partition(a, lo, hi);24 quickSort(a, lo, p - 1);25 quickSort(a, p + 1, hi);26}27
28int main() {29 std::vector<int> data = {10, 7, 8, 9, 1, 5};30 std::cout << "Before: ";31 printVec(data);32 quickSort(data, 0, static_cast<int>(data.size()) - 1);33 std::cout << "After: ";34 printVec(data);35 return 0;36}Codice Quick Sort in C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void swap(int* x, int* y) {9 int tmp = *x;10 *x = *y;11 *y = tmp;12}13
14// Lomuto partition: place the pivot in its final position15int partition(int a[], int lo, int hi) {16 int pivot = a[hi];17 int i = lo;18 for (int j = lo; j < hi; j++) {19 if (a[j] < pivot) swap(&a[i++], &a[j]);20 }21 swap(&a[i], &a[hi]);22 return i;23}24
25void quickSort(int a[], int lo, int hi) {26 if (lo >= hi) return;27 int p = partition(a, lo, hi);28 quickSort(a, lo, p - 1);29 quickSort(a, p + 1, hi);30}31
32int main(void) {33 int data[] = {10, 7, 8, 9, 1, 5};34 int n = sizeof(data) / sizeof(data[0]);35 printf("Before: ");36 printArr(data, n);37 quickSort(data, 0, n - 1);38 printf("After: ");39 printArr(data, n);40 return 0;41}Codice Quick Sort in Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211DECLARE i : INTEGER12
13FUNCTION partition(lo : INTEGER, hi : INTEGER) RETURNS INTEGER14 DECLARE pivot : INTEGER15 DECLARE a : INTEGER16 DECLARE b : INTEGER17 DECLARE temp : INTEGER18 pivot ← nums[hi]19 a ← lo - 120 FOR b ← lo TO hi - 121 IF nums[b] <= pivot THEN22 a ← a + 123 temp ← nums[a]24 nums[a] ← nums[b]25 nums[b] ← temp26 ENDIF27 NEXT b28 temp ← nums[a + 1]29 nums[a + 1] ← nums[hi]30 nums[hi] ← temp31 RETURN a + 132ENDFUNCTION33
34PROCEDURE quickSort(lo : INTEGER, hi : INTEGER)35 DECLARE p : INTEGER36 IF lo < hi THEN37 // Place the pivot, then sort each side of it38 p ← partition(lo, hi)39 CALL quickSort(lo, p - 1)40 CALL quickSort(p + 1, hi)41 ENDIF42ENDPROCEDURE43
44CALL quickSort(1, n)45
46FOR i ← 1 TO n47 OUTPUT nums[i]48NEXT iDomande frequenti sul quick sort
Qual è la complessità temporale del quicksort?
Il quicksort è in media
O(n log n) ed è O(n log n) nel caso migliore, ma degrada a O(n²) nel caso peggiore, quando le partizioni sono sempre sbilanciate. I pivot casuali o con la mediana di tre rendono il caso peggiore molto improbabile.Il quicksort è stabile?
No. La partizione standard in loco scambia elementi lontani tra loro, cosa che può cambiare l'ordine relativo delle chiavi uguali. Esistono varianti stabili, ma rinunciano al vantaggio del quicksort di lavorare in loco.
Perché il quicksort è spesso più veloce del merge sort?
Il quicksort partiziona in loco con un'ottima località della cache e senza buffer extra, quindi i suoi fattori costanti sono piccoli. Il merge sort ha lo stesso limite
O(n log n), ma paga un buffer O(n) e più spostamenti di dati.Quicksort o merge sort: quale usare?
Scegli il quicksort per ordinare in loco e velocemente array in memoria, dove i suoi fattori costanti piccoli di solito vincono. Scegli il merge sort quando ti serve un ordinamento stabile, un caso peggiore
O(n log n) garantito, o quando ordini liste concatenate o dati esterni che non stanno in RAM.Perché il quicksort diventa O(n²) su un array ordinato?
Con un pivot fisso, come il primo o l'ultimo elemento, un input già ordinato fa sì che ogni partizione stacchi un solo elemento, producendo
n livelli di ricorsione invece di log n. Scegliere il pivot a caso o con la mediana di tre rompe questo schema e riporta il comportamento a O(n log n).Qual è la differenza tra gli schemi di partizione di Lomuto e di Hoare?
Lo schema di Lomuto usa un solo indice che scorre da sinistra a destra ed è più semplice da scrivere, ed è per questo che questa visualizzazione lo usa. Lo schema di Hoare usa due puntatori che si muovono verso il centro e di solito fa meno scambi, quindi in pratica è più veloce, ma non colloca il pivot nella sua posizione finale durante il passo di partizione.
Risorse correlate
Altre visualizzazioni
