Ordinamento rapido è un algoritmo di ordinamento basato su Algoritmo Dividi e Impera che sceglie un elemento come pivot e suddivide l'array dato attorno al pivot selezionato posizionando il pivot nella sua posizione corretta nell'array ordinato.
Come funziona QuickSort?
Pratica consigliata Ordinamento rapido Provalo!Il processo chiave in QuickSort è un partizione() . L'obiettivo delle partizioni è posizionare il pivot (qualsiasi elemento può essere scelto come pivot) nella sua posizione corretta nell'array ordinato e mettere tutti gli elementi più piccoli a sinistra del pivot e tutti gli elementi più grandi a destra del pivot .
La partizione viene eseguita in modo ricorsivo su ciascun lato del pivot dopo che il pivot è stato posizionato nella sua posizione corretta e questo ordina infine l'array.
Come funziona Quicksort
disattivando la modalità sviluppatore
Scelta del perno:
Esistono molte scelte diverse per la scelta dei pivot.
- Scegli sempre il primo elemento come pivot .
- Scegli sempre l'ultimo elemento come pivot (implementato di seguito)
- Scegli un elemento casuale come pivot .
- Scegli il centro come perno.
Algoritmo di partizione:
La logica è semplice, partiamo dall'elemento più a sinistra e teniamo traccia dell'indice degli elementi più piccoli (o uguali). io . Durante l'attraversamento, se troviamo un elemento più piccolo, scambiamo l'elemento corrente con arr[i]. Altrimenti, ignoriamo l'elemento corrente.
Cerchiamo di comprendere il funzionamento della partizione e l'algoritmo Quick Sort con l'aiuto del seguente esempio:
Considera: arr[] = {10, 80, 30, 90, 40}.
- Confronta 10 con il perno e poiché è inferiore al perno disponili in modo corrispondente.
Partizione in QuickSort: confronta pivot con 10
- Confronta 80 con il perno. È maggiore del perno.
Partizione in QuickSort: confronta pivot con 80
- Confronta 30 con pivot. È inferiore al perno, quindi sistemalo di conseguenza.
Partizione in QuickSort: confronta pivot con 30
- Confronta 90 con il perno. È maggiore del perno.
Partizione in QuickSort: confronta pivot con 90
quando è uscito windows 7?
- Disporre il perno nella sua posizione corretta.
Partizione in QuickSort: posiziona il perno nella posizione corretta
Illustrazione di Quicksort:
Poiché il processo di partizione viene eseguito in modo ricorsivo, continua a posizionare il perno nella sua posizione effettiva nell'array ordinato. Mettere ripetutamente i perni nella loro posizione effettiva rende l'array ordinato.
Segui le immagini seguenti per capire come l'implementazione ricorsiva dell'algoritmo di partizione aiuta a ordinare l'array.
checkout in git
- Partizione iniziale sull'array principale:
Quicksort: esecuzione della partizione
- Partizionamento dei sottoarray:
Quicksort: esecuzione della partizione
Implementazione del codice del Quick Sort:
C++ #include using namespace std; int partition(int arr[],int low,int high) { //choose the pivot int pivot=arr[high]; //Index of smaller element and Indicate //the right position of pivot found so far int i=(low-1); for(int j=low;j<=high-1;j++) { //If current element is smaller than the pivot if(arr[j] C // C program for QuickSort #include // Utility function to swap tp integers void swap(int* p1, int* p2) { int temp; temp = *p1; *p1 = *p2; *p2 = temp; } int partition(int arr[], int low, int high) { // choose the pivot int pivot = arr[high]; // Index of smaller element and Indicate // the right position of pivot found so far int i = (low - 1); for (int j = low; j <= high - 1; j++) { // If current element is smaller than the pivot if (arr[j] < pivot) { // Increment index of smaller element i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } // The Quicksort function Implement void quickSort(int arr[], int low, int high) { // when low is less than high if (low < high) { // pi is the partition return index of pivot int pi = partition(arr, low, high); // Recursion Call // smaller element than pivot goes left and // higher element goes right quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } int main() { int arr[] = { 10, 7, 8, 9, 1, 5 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call quickSort(arr, 0, n - 1); // Print the sorted array printf('Sorted Array
'); for (int i = 0; i < n; i++) { printf('%d ', arr[i]); } return 0; } // This Code is Contributed By Diwakar Jha> Giava // Java implementation of QuickSort import java.io.*; class GFG { // A utility function to swap two elements static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // This function takes last element as pivot, // places the pivot element at its correct position // in sorted array, and places all smaller to left // of pivot and all greater elements to right of pivot static int partition(int[] arr, int low, int high) { // Choosing the pivot int pivot = arr[high]; // Index of smaller element and indicates // the right position of pivot found so far int i = (low - 1); for (int j = low; j <= high - 1; j++) { // If current element is smaller than the pivot if (arr[j] < pivot) { // Increment index of smaller element i++; swap(arr, i, j); } } swap(arr, i + 1, high); return (i + 1); } // The main function that implements QuickSort // arr[] -->Array da ordinare, // basso --> Indice iniziale, // alto --> Indice finale static void quickSort(int[] arr, int low, int high) { if (low< high) { // pi is partitioning index, arr[p] // is now at right place int pi = partition(arr, low, high); // Separately sort elements before // partition and after partition quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } // To print sorted array public static void printArr(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + ' '); } } // Driver Code public static void main(String[] args) { int[] arr = { 10, 7, 8, 9, 1, 5 }; int N = arr.length; // Function call quickSort(arr, 0, N - 1); System.out.println('Sorted array:'); printArr(arr); } } // This code is contributed by Ayush Choudhary // Improved by Ajay Virmoti> Pitone # Python3 implementation of QuickSort # Function to find the partition position def partition(array, low, high): # Choose the rightmost element as pivot pivot = array[high] # Pointer for greater element i = low - 1 # Traverse through all elements # compare each element with pivot for j in range(low, high): if array[j] <= pivot: # If element smaller than pivot is found # swap it with the greater element pointed by i i = i + 1 # Swapping element at i with element at j (array[i], array[j]) = (array[j], array[i]) # Swap the pivot element with # the greater element specified by i (array[i + 1], array[high]) = (array[high], array[i + 1]) # Return the position from where partition is done return i + 1 # Function to perform quicksort def quicksort(array, low, high): if low < high: # Find pivot element such that # element smaller than pivot are on the left # element greater than pivot are on the right pi = partition(array, low, high) # Recursive call on the left of pivot quicksort(array, low, pi - 1) # Recursive call on the right of pivot quicksort(array, pi + 1, high) # Driver code if __name__ == '__main__': array = [10, 7, 8, 9, 1, 5] N = len(array) # Function call quicksort(array, 0, N - 1) print('Sorted array:') for x in array: print(x, end=' ') # This code is contributed by Adnan Aliakbar> C# // C# implementation of QuickSort using System; class GFG { // A utility function to swap two elements static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // This function takes last element as pivot, // places the pivot element at its correct position // in sorted array, and places all smaller to left // of pivot and all greater elements to right of pivot static int partition(int[] arr, int low, int high) { // Choosing the pivot int pivot = arr[high]; // Index of smaller element and indicates // the right position of pivot found so far int i = (low - 1); for (int j = low; j <= high - 1; j++) { // If current element is smaller than the pivot if (arr[j] < pivot) { // Increment index of smaller element i++; swap(arr, i, j); } } swap(arr, i + 1, high); return (i + 1); } // The main function that implements QuickSort // arr[] -->Array da ordinare, // basso --> Indice iniziale, // alto --> Indice finale static void quickSort(int[] arr, int low, int high) { if (low< high) { // pi is partitioning index, arr[p] // is now at right place int pi = partition(arr, low, high); // Separately sort elements before // and after partition index quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } // Driver Code public static void Main() { int[] arr = { 10, 7, 8, 9, 1, 5 }; int N = arr.Length; // Function call quickSort(arr, 0, N - 1); Console.WriteLine('Sorted array:'); for (int i = 0; i < N; i++) Console.Write(arr[i] + ' '); } } // This code is contributed by gfgking> JavaScript // Function to partition the array and return the partition index function partition(arr, low, high) { // Choosing the pivot let pivot = arr[high]; // Index of smaller element and indicates the right position of pivot found so far let i = low - 1; for (let j = low; j <= high - 1; j++) { // If current element is smaller than the pivot if (arr[j] < pivot) { // Increment index of smaller element i++; [arr[i], arr[j]] = [arr[j], arr[i]]; // Swap elements } } [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // Swap pivot to its correct position return i + 1; // Return the partition index } // The main function that implements QuickSort function quickSort(arr, low, high) { if (low < high) { // pi is the partitioning index, arr[pi] is now at the right place let pi = partition(arr, low, high); // Separately sort elements before partition and after partition quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } // Driver code let arr = [10, 7, 8, 9, 1, 5]; let N = arr.length; // Function call quickSort(arr, 0, N - 1); console.log('Sorted array:'); console.log(arr.join(' '));> PHP // code ?>// Questa funzione prende il posto dell'ultimo elemento come pivot // Posiziona il pivot nella posizione corretta // Nell'array ordinato e posiziona tutti gli elementi più piccoli a sinistra // del pivot e tutti gli elementi maggiori alla sua destra della funzione pivot (&$arr, $low,$high) { // Scegli l'elemento pivot $pivot= $arr[$high]; // Indice dell'elemento più piccolo e indica // La giusta posizione del pivot $i=($low-1); for($j=$basso;$j<=$high-1;$j++) { if($arr[$j]<$pivot) { // Increment index of smaller element $i++; list($arr[$i],$arr[$j])=array($arr[$j],$arr[$i]); } } // Pivot element as correct position list($arr[$i+1],$arr[$high])=array($arr[$high],$arr[$i+1]); return ($i+1); } // The main function that implement as QuickSort // arr[]:- Array to be sorted // low:- Starting Index //high:- Ending Index function quickSort(&$arr,$low,$high) { if($low<$high) { // pi is partition $pi= partition($arr,$low,$high); // Sort the array // Before the partition of Element quickSort($arr,$low,$pi-1); // After the partition Element quickSort($arr,$pi+1,$high); } } // Driver Code $arr= array(10,7,8,9,1,5); $N=count($arr); // Function Call quickSort($arr,0,$N-1); echo 'Sorted Array:
'; for($i=0;$i<$N;$i++) { echo $arr[$i]. ' '; } //This code is contributed by Diwakar Jha> Produzione
Sorted Array 1 5 7 8 9 10>
Analisi della complessità dell'ordinamento rapido :
Complessità temporale:
- Caso migliore : Ω (N log (N))
Lo scenario migliore per il Quicksort si verifica quando il pivot scelto in ogni passaggio divide l'array in metà più o meno uguali.
In questo caso, l'algoritmo creerà partizioni bilanciate, portando a un ordinamento efficiente. - Caso medio: θ ( N log (N))
Le prestazioni nel caso medio di Quicksort sono generalmente molto buone nella pratica, rendendolo uno degli algoritmi di ordinamento più veloci. - Caso peggiore: O(N2)
Lo scenario peggiore per Quicksort si verifica quando il pivot in ogni passaggio risulta costantemente in partizioni altamente sbilanciate. Quando l'array è già ordinato e il pivot viene sempre scelto come elemento più piccolo o più grande. Per mitigare lo scenario peggiore, vengono utilizzate varie tecniche come la scelta di un buon pivot (ad esempio, mediana di tre) e l'utilizzo dell'algoritmo randomizzato (Randomized Quicksort) per mescolare l'elemento prima dell'ordinamento. - Spazio ausiliario: O(1), se non consideriamo lo stack space ricorsivo. Se consideriamo lo spazio dello stack ricorsivo, nel peggiore dei casi potrebbe verificarsi Quicksort O ( N ).
Vantaggi dell'ordinamento rapido:
- È un algoritmo divide et impera che semplifica la risoluzione dei problemi.
- È efficiente su set di dati di grandi dimensioni.
- Ha un sovraccarico basso, poiché richiede solo una piccola quantità di memoria per funzionare.
Svantaggi dell'ordinamento rapido:
- Ha una complessità temporale nel caso peggiore pari a O(N2), che si verifica quando il pivot viene scelto male.
- Non è una buona scelta per set di dati di piccole dimensioni.
- Non è un ordinamento stabile, nel senso che se due elementi hanno la stessa chiave, il loro ordine relativo non verrà conservato nell'output ordinato in caso di ordinamento rapido, perché qui stiamo scambiando gli elementi in base alla posizione del pivot (senza considerare il loro ordinamento originale posizioni).