Algoritmo QuickSort

Sommario

Come funziona QuickSort?
Algoritmo di ordinamento rapido
Esempi di Python, Java e C / C ++
Complessità Quicksort
Applicazioni Quicksort

In questo tutorial imparerai come funziona Quicksort. Inoltre, troverai esempi funzionanti di quicksort in C, C ++ Python e Java.

Quicksort è un algoritmo basato sull'approccio divide et impera in cui l'array è suddiviso in sottoarray e questi sotto-array vengono chiamati ricorsivamente per ordinare gli elementi.

Come funziona QuickSort?

Un elemento pivot viene scelto dall'array. Puoi scegliere qualsiasi elemento dall'array come elemento pivot.
Qui, abbiamo preso il più a destra (cioè l'ultimo elemento) dell'array come elemento pivot. Seleziona un elemento pivot
Gli elementi più piccoli dell'elemento pivot vengono messi a sinistra e gli elementi più grandi dell'elemento pivot vengono messi a destra. Posizionare tutti gli elementi più piccoli a sinistra e quelli maggiori a destra dell'elemento perno.
La disposizione di cui sopra si ottiene con i seguenti passaggi.
1. Un puntatore è fissato all'elemento pivot. L'elemento pivot viene confrontato con gli elementi a partire dal primo indice. Se viene raggiunto l'elemento maggiore dell'elemento pivot, viene impostato un secondo puntatore per quell'elemento.
2. Ora, l'elemento pivot viene confrontato con gli altri elementi (un terzo puntatore). Se viene raggiunto un elemento più piccolo dell'elemento pivot, l'elemento più piccolo viene scambiato con l'elemento più grande trovato in precedenza. Confronto dell'elemento pivot con altri elementi
3. Il processo continua fino a raggiungere il penultimo elemento.
  Infine, l'elemento pivot viene scambiato con il secondo puntatore. Scambia l'elemento pivot con il secondo puntatore
4. Ora le sottoparti sinistra e destra di questo elemento pivot vengono prese per ulteriori elaborazioni nei passaggi seguenti.
Gli elementi pivot vengono nuovamente scelti separatamente per le sottoparti sinistra e destra. All'interno di queste sottoparti, gli elementi perno sono posti nella loro giusta posizione. Quindi, viene ripetuto il passaggio 2. Seleziona l'elemento pivot in ciascuna metà e posizionalo nella posizione corretta usando la ricorsione
Le sottoparti vengono nuovamente suddivise in sottoparti più piccole fino a quando ciascuna sottoparte è formata da un unico elemento.
A questo punto, l'array è già ordinato.

Quicksort utilizza la ricorsione per ordinare le sottoparti.

Sulla base dell'approccio Divide and conquer, l'algoritmo quicksort può essere spiegato come:

Dividi
L'array è diviso in sottoparti prendendo pivot come punto di partizionamento. Gli elementi più piccoli del perno vengono posizionati a sinistra del perno e gli elementi più grandi del perno vengono posizionati a destra.
Conquista
Le sottoparti sinistra e destra vengono nuovamente partizionate usando il selezionando gli elementi pivot per loro. Ciò può essere ottenuto passando ricorsivamente le sottoparti nell'algoritmo.
Combina
Questo passaggio non ha un ruolo significativo nel Quicksort. L'array è già ordinato alla fine della fase di conquista.

Puoi capire il funzionamento di Quicksort con l'aiuto delle illustrazioni seguenti.

Ordinamento degli elementi a sinistra del pivot utilizzando la ricorsione

Ordinamento degli elementi a destra del pivot utilizzando la ricorsione

Algoritmo di ordinamento rapido

 quickSort (array, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- partition (array, leftmostIndex, rightmostIndex) quickSort (array, leftmostIndex, pivotIndex) quickSort (array, pivotIndex + 1, rightmostIndex leftmostIndex, array ) imposta rightmostIndex come pivotIndex storeIndex <- leftmostIndex - 1 for i <- leftmostIndex + 1 a rightmostIndex if element (i) <pivotElement swap element (i) and element (storeIndex) storeIndex ++ swap pivotElement and element (storeIndex + 1) return storeIndex + 1

Esempi di Python, Java e C / C ++

Python Java C C +

 # Quick sort in Python # Function to partition the array on the basis of pivot element def partition(array, low, high): # Select the pivot element pivot = array(high) i = low - 1 # Put the elements smaller than pivot on the left and greater #than pivot on the right of pivot for j in range(low, high): if array(j) <= pivot: i = i + 1 (array(i), array(j)) = (array(j), array(i)) (array(i + 1), array(high)) = (array(high), array(i + 1)) return i + 1 def quickSort(array, low, high): if low < high: # Select pivot position and put all the elements smaller # than pivot on left and greater than pivot on right pi = partition(array, low, high) # Sort the elements on the left of pivot quickSort(array, low, pi - 1) # Sort the elements on the right of pivot quickSort(array, pi + 1, high) data = (8, 7, 2, 1, 0, 9, 6) size = len(data) quickSort(data, 0, size - 1) print('Sorted Array in Ascending Order:') print(data)

 // Quick sort in Java import java.util.Arrays; class QuickSort ( // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left and // greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; int temp = array(i); array(i) = array(j); array(j) = temp; ) ) int temp = array(i + 1); array(i + 1) = array(high); array(high) = temp; return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code public static void main(String args()) ( int() data = ( 8, 7, 2, 1, 0, 9, 6 ); int size = data.length; QuickSort qs = new QuickSort(); qs.quickSort(data, 0, size - 1); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )

 // Quick sort in C #include // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Function to print eklements of an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (8, 7, 2, 1, 0, 9, 6); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); printf("Sorted array in ascending order: "); printArray(data, n); )

 // Quick sort in C++ #include using namespace std; // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to print eklements of an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) printArray(array, 7); cout << "… "; swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code int main() ( int data() = (8, 7, 6, 1, 0, 9, 2); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); cout << "Sorted array in ascending order: "; printArray(data, n); )

Complessità Quicksort

Complessità temporali

Worst Case Complexity (Big-O) : si verifica quando l'elemento pivot selezionato è l'elemento più grande o più piccolo. Questa condizione porta al caso in cui l'elemento pivot si trova in un'estremità estrema dell'array ordinato. Un sotto-array è sempre vuoto e un altro sotto-array contiene elementi. Pertanto, quicksort viene chiamato solo su questo sotto-array. Tuttavia, l'algoritmo di ordinamento rapido offre prestazioni migliori per i perni sparsi.O(n²)
n - 1
Best Case Complexity (Big-omega) : O(n*log n)
si verifica quando l'elemento pivot è sempre l'elemento centrale o vicino all'elemento centrale.
Complessità case media (Big-theta) : O(n*log n)
si verifica quando le condizioni di cui sopra non si verificano.