ALGORITMIDi ORDINAMENTO
Quick Sort
start_
Funzionamento dell'algoritmo
Esempio sviluppo dell'algoritmo
Che cos'è il Quick Sort?
Implementazione algoritmo
cos'è il quick sort?
Il quick sort è un algoritmo di ordinamento ricorsivo in loco (o in place), in particolare utilizza il metodo divide et impera per ordinare i dati di un vettore. La procedura ricorsiva avviene nel seguente modo: viene scelto un elemento dall’array, detto pivot, si posizionano gli elementi minori a sinistra del pivot, mentre gli elementi più grandi a destra.
Il processo verrà ripetuto in ciascun sottogruppo fino a che il vettore non sarà completamente ordinato.
Il Quick Sort è rinomato per le sue prestazioni superiori rispetto ad altri algoritmi di ordinamento basati su confronti.
funzionamento dell'algoritmo
Esempio in c
Scegliamo come Pivot il primo elemento,dunque Pivot = 4.
Dobbiamo avere a sinistra gli elementi minori di Pivot, a destra gli elementi maggiori.
Facciamo partire l’indice i da sinistra ovvero dal primo elemento e l’indice j da destra ovvero dall’ultimo elemento.
Per comodità ci riferiremo a primo e ultimo per vedere in dettaglio tutti i passaggi.
Dapprima avremo:
Pivot = 4 (si trova in posizione i)
primo = 4
ultimo = 8
Esempio in c
Ci chiediamo Pivot è minore di ultimo? Cioè 4 è minore di 8?
Si, allora procedo e sposto l’indice j (perchè a destra devo avere gli elementi maggiori, quindi non devo scambiarli!)
Quindi avremo:
Pivot=4 (si trova in posizione i)
primo=4
ultimo=3
Esempio in c
Ci poniamo allora la domanda Pivot è minore di ultimo? No, allora sposto Pivot in posizione j, cioè in ultimo. Quindi avrò il terzo passaggio: Pivot=4 (si trova in posizione j) primo=3 ultimo=4
Esempio in c
Adesso Pivot è in posizione indicata dall’indice j, dunque sposto l’indice i. Mi chiedo Pivot è maggiore di primo? Si, allora sposto l’indice i. E continuo spostando l’indice i fino all’elemento 5. Quindi avrò: Pivot = 4 (si trova in posizione j) primo = 5 ultimo = 4
Esempio in c
Mi chiedo ancora Pivot è maggiore di primo?
No, allora sostituisco Pivot nella posizione di primo.
Quindi avrò:
Pivot = 4 (si trova in posizione i)
primo = 4
ultimo = 5
Esempio in c
Adesso Pivot si trova in posizione i, facciamo muovere j.
Cioè Pivot è minore di ultimo? Si allora sposto l’indice j e avrò:
Pivot=4 (si trova in posizione i)
primo=4
ultimo=0
Esempio in c
Pivot è minore di ultimo ?
No allora li scambiamo. Avremo:
Pivot = 4 (si trova in posizione j)
primo = 0
ultimo = 4
Esempio in c
Quindi ci chiediamo Pivot è maggiore di primo? Si, allora spostiamo l’indice i e avremo la situazione:
Pivot = 4 (si trova in posizione i) primo = 4 ultimo = 2
Pivot è minore di primo?
Si allora l’indice i coinciderà con j.
Adesso che abbiamo a destra gli elementi maggiori del Pivot e a sinistra gli elementi minori dobbiamo procedere con l’ordinamento dei due sotto-array procedendo allo stesso modo.
implementazione algoritmo
Dopo aver definito un array di numeri, lo ordiniamo con Quick Sort, passando l'array, il primo e l'ultimo indice.
Nella funzione, verifichiamo che low sia minore di high e assegnamo a pivot l'indice del primo elemento.
Next
implementazione algoritmo
printf
void
Utilizzando vari cicli while controlliamo se il valore contenuto nell’array nella posizione i sia minore o uguale al valore nella posizione del pivot, se si incrementiamo la variabile i. Analogamente, controlliamo se il valore nella posizione j è maggiore del valore nella posizione pivot, se si decrementano la variabile j.
quicksort
define
include
temp
while
Next
implementazione algoritmo
Se questi due cicli while non sono più verificati e se la variabile i è ancora minore di j, invertiamo i due valori che si trovano in tali posizioni. Quando la variabile i diventa maggiore o uguale alla variabile j, termina il ciclo while esterno e invertiamo tra loro i valori che si trovano nella posizione j e pivot.
ALGORITMO
Next
SITOGRAFIA
https://www.learnex.it/https://www.codingcreativo.it/ https://www.programiz.com/ https://www.geeksforgeeks.org/ https://it.wikipedia.org/ Vitale Chiara Elaborato competenze digitali
Funzionamento :
Selezione del Pivot: Si sceglie un elemento centrale dal vettore, noto come “pivot”, e lo si memorizza in una variabile.
Suddivisione dell’Array: Gli elementi maggiori o uguali al pivot vengono posizionati a sinistra, mentre quelli minori vengono posizionati a destra. Questo processo di suddivisione crea due sotto-array separati.
Ordinamento Ricorsivo: Si applica ricorsivamente l’algoritmo Quick Sort ai sotto-array sinistro e destro.
La procedura che si occupa della suddivisione dell’array in due parti, posizionando correttamente gli elementi rispetto al pivot, è comunemente chiamata “partition”.
Divide et Impara
Divide: L’array viene suddiviso in sotto-array più piccoli, generalmente utilizzando un elemento chiamato “pivot”.
Impera: I sotto-array vengono ordinati in maniera ricorsiva ( l’algoritmo si richiama su se stesso per ordinare i sotto-array).
Combina: Una volta ordinati i sotto-array, i risultati vengono combinati per ottenere l’array ordinato finale.
#include <stdio.h>
#define N 10
void quicksort(int l[], int low, int high){
int i, j, pivot, temp;
if(low < high){
pivot = low;
i = low;
j = high;
while(i < j){
while(l[i] <= l[pivot] && i < high)
i++;
while(l[j] > l[pivot])
j--;
if(i < j){
temp = l[i];
l[i] = l[j];
l[j] = temp;
}
}
temp = l[pivot];
l[pivot] = l[j];
l[j] = temp;
quicksort(l, low, j - 1);
quicksort(l, j + 1, high);
}
}
int main(){
int lista[N] = {6, 2, 4, 7, 5, 1, 9, 3, 15, 22};
quicksort(lista, 0, N - 1);
printf("Array ordinato: ");
for(int i = 0; i < N; i++){
printf("%d ", lista[i]);
}
return 0;
}
// Output: Array ordinato: 1 2 3 4 5 6 7 9 15 22
PIVOT
Esistono molte possibilità diverse per la scelta dei perni.
Scegli sempre il primo (o l'ultimo) elemento come pivot . L'implementazione sottostante sceglie l'ultimo elemento come pivot. Il problema con questo approccio è che finisce nel caso peggiore quando l'array è già ordinato.
Scegli un elemento casuale come pivot . Questo è un approccio preferito perché non ha uno schema per cui si verifica il caso peggiore.
Scegli l'elemento mediano come pivot. Questo è un approccio ideale in termini di complessità temporale, poiché possiamo trovare la mediana in tempo lineare e la funzione di partizione dividerà sempre l'array di input in due metà. Ma richiede più tempo in media, poiché la ricerca della mediana ha costanti elevate.
ALGORITMI Di ORDINAMENTO
Chiara Vitale
Created on March 16, 2025
Quick Sort
Start designing with a free template
Discover more than 1500 professional designs like these:
View
January School Calendar
View
Genial Calendar 2026
View
Annual calendar 2026
View
School Calendar 2026
View
2026 calendar
View
January Higher Education Academic Calendar
View
School Year Calendar January
Explore all templates
Transcript
ALGORITMIDi ORDINAMENTO
Quick Sort
start_
Funzionamento dell'algoritmo
Esempio sviluppo dell'algoritmo
Che cos'è il Quick Sort?
Implementazione algoritmo
cos'è il quick sort?
Il quick sort è un algoritmo di ordinamento ricorsivo in loco (o in place), in particolare utilizza il metodo divide et impera per ordinare i dati di un vettore. La procedura ricorsiva avviene nel seguente modo: viene scelto un elemento dall’array, detto pivot, si posizionano gli elementi minori a sinistra del pivot, mentre gli elementi più grandi a destra. Il processo verrà ripetuto in ciascun sottogruppo fino a che il vettore non sarà completamente ordinato.
Il Quick Sort è rinomato per le sue prestazioni superiori rispetto ad altri algoritmi di ordinamento basati su confronti.
funzionamento dell'algoritmo
Esempio in c
Scegliamo come Pivot il primo elemento,dunque Pivot = 4. Dobbiamo avere a sinistra gli elementi minori di Pivot, a destra gli elementi maggiori. Facciamo partire l’indice i da sinistra ovvero dal primo elemento e l’indice j da destra ovvero dall’ultimo elemento. Per comodità ci riferiremo a primo e ultimo per vedere in dettaglio tutti i passaggi. Dapprima avremo: Pivot = 4 (si trova in posizione i) primo = 4 ultimo = 8
Esempio in c
Ci chiediamo Pivot è minore di ultimo? Cioè 4 è minore di 8? Si, allora procedo e sposto l’indice j (perchè a destra devo avere gli elementi maggiori, quindi non devo scambiarli!) Quindi avremo: Pivot=4 (si trova in posizione i) primo=4 ultimo=3
Esempio in c
Ci poniamo allora la domanda Pivot è minore di ultimo? No, allora sposto Pivot in posizione j, cioè in ultimo. Quindi avrò il terzo passaggio: Pivot=4 (si trova in posizione j) primo=3 ultimo=4
Esempio in c
Adesso Pivot è in posizione indicata dall’indice j, dunque sposto l’indice i. Mi chiedo Pivot è maggiore di primo? Si, allora sposto l’indice i. E continuo spostando l’indice i fino all’elemento 5. Quindi avrò: Pivot = 4 (si trova in posizione j) primo = 5 ultimo = 4
Esempio in c
Mi chiedo ancora Pivot è maggiore di primo? No, allora sostituisco Pivot nella posizione di primo. Quindi avrò: Pivot = 4 (si trova in posizione i) primo = 4 ultimo = 5
Esempio in c
Adesso Pivot si trova in posizione i, facciamo muovere j. Cioè Pivot è minore di ultimo? Si allora sposto l’indice j e avrò: Pivot=4 (si trova in posizione i) primo=4 ultimo=0
Esempio in c
Pivot è minore di ultimo ? No allora li scambiamo. Avremo: Pivot = 4 (si trova in posizione j) primo = 0 ultimo = 4
Esempio in c
Quindi ci chiediamo Pivot è maggiore di primo? Si, allora spostiamo l’indice i e avremo la situazione: Pivot = 4 (si trova in posizione i) primo = 4 ultimo = 2
Pivot è minore di primo? Si allora l’indice i coinciderà con j. Adesso che abbiamo a destra gli elementi maggiori del Pivot e a sinistra gli elementi minori dobbiamo procedere con l’ordinamento dei due sotto-array procedendo allo stesso modo.
implementazione algoritmo
Dopo aver definito un array di numeri, lo ordiniamo con Quick Sort, passando l'array, il primo e l'ultimo indice. Nella funzione, verifichiamo che low sia minore di high e assegnamo a pivot l'indice del primo elemento.
Next
implementazione algoritmo
printf
void
Utilizzando vari cicli while controlliamo se il valore contenuto nell’array nella posizione i sia minore o uguale al valore nella posizione del pivot, se si incrementiamo la variabile i. Analogamente, controlliamo se il valore nella posizione j è maggiore del valore nella posizione pivot, se si decrementano la variabile j.
quicksort
define
include
temp
while
Next
implementazione algoritmo
Se questi due cicli while non sono più verificati e se la variabile i è ancora minore di j, invertiamo i due valori che si trovano in tali posizioni. Quando la variabile i diventa maggiore o uguale alla variabile j, termina il ciclo while esterno e invertiamo tra loro i valori che si trovano nella posizione j e pivot.
ALGORITMO
Next
SITOGRAFIA
https://www.learnex.it/https://www.codingcreativo.it/ https://www.programiz.com/ https://www.geeksforgeeks.org/ https://it.wikipedia.org/ Vitale Chiara Elaborato competenze digitali
Funzionamento :
Selezione del Pivot: Si sceglie un elemento centrale dal vettore, noto come “pivot”, e lo si memorizza in una variabile. Suddivisione dell’Array: Gli elementi maggiori o uguali al pivot vengono posizionati a sinistra, mentre quelli minori vengono posizionati a destra. Questo processo di suddivisione crea due sotto-array separati. Ordinamento Ricorsivo: Si applica ricorsivamente l’algoritmo Quick Sort ai sotto-array sinistro e destro. La procedura che si occupa della suddivisione dell’array in due parti, posizionando correttamente gli elementi rispetto al pivot, è comunemente chiamata “partition”.
Divide et Impara
Divide: L’array viene suddiviso in sotto-array più piccoli, generalmente utilizzando un elemento chiamato “pivot”. Impera: I sotto-array vengono ordinati in maniera ricorsiva ( l’algoritmo si richiama su se stesso per ordinare i sotto-array). Combina: Una volta ordinati i sotto-array, i risultati vengono combinati per ottenere l’array ordinato finale.
#include <stdio.h> #define N 10 void quicksort(int l[], int low, int high){ int i, j, pivot, temp; if(low < high){ pivot = low; i = low; j = high; while(i < j){ while(l[i] <= l[pivot] && i < high) i++; while(l[j] > l[pivot]) j--; if(i < j){ temp = l[i]; l[i] = l[j]; l[j] = temp; } } temp = l[pivot]; l[pivot] = l[j]; l[j] = temp; quicksort(l, low, j - 1); quicksort(l, j + 1, high); } } int main(){ int lista[N] = {6, 2, 4, 7, 5, 1, 9, 3, 15, 22}; quicksort(lista, 0, N - 1); printf("Array ordinato: "); for(int i = 0; i < N; i++){ printf("%d ", lista[i]); } return 0; } // Output: Array ordinato: 1 2 3 4 5 6 7 9 15 22
PIVOT
Esistono molte possibilità diverse per la scelta dei perni. Scegli sempre il primo (o l'ultimo) elemento come pivot . L'implementazione sottostante sceglie l'ultimo elemento come pivot. Il problema con questo approccio è che finisce nel caso peggiore quando l'array è già ordinato. Scegli un elemento casuale come pivot . Questo è un approccio preferito perché non ha uno schema per cui si verifica il caso peggiore. Scegli l'elemento mediano come pivot. Questo è un approccio ideale in termini di complessità temporale, poiché possiamo trovare la mediana in tempo lineare e la funzione di partizione dividerà sempre l'array di input in due metà. Ma richiede più tempo in media, poiché la ricerca della mediana ha costanti elevate.