Dans ce didacticiel, vous apprendrez comment fonctionne le tri rapide. Vous trouverez également des exemples de travail de tri rapide en C, C ++ Python et Java.
Quicksort est un algorithme basé sur une approche de division et de conquête dans laquelle le tableau est divisé en sous-tableaux et ces sous-tableaux sont appelés de manière récursive pour trier les éléments.
Comment fonctionne QuickSort?
- Un élément pivot est choisi dans le tableau. Vous pouvez choisir n'importe quel élément du tableau comme élément pivot.
Ici, nous avons pris le plus à droite (c'est-à-dire le dernier élément) du tableau comme élément pivot.
Sélectionnez un élément pivot - Les éléments plus petits que l'élément pivot sont placés à gauche et les éléments plus grands que l'élément pivot sont placés à droite.
Placez tous les éléments les plus petits à gauche et les plus grands à droite de l'élément pivot.
La disposition ci-dessus est obtenue par les étapes suivantes.- Un pointeur est fixé sur l'élément pivot. L'élément pivot est comparé aux éléments à partir du premier index. Si l'élément supérieur à l'élément pivot est atteint, un deuxième pointeur est défini pour cet élément.
- Maintenant, l'élément pivot est comparé aux autres éléments (un troisième pointeur). Si un élément plus petit que l'élément pivot est atteint, le plus petit élément est remplacé par l'élément le plus grand trouvé précédemment.
Comparaison de l'élément pivot avec d'autres éléments - Le processus se poursuit jusqu'à ce que l'avant-dernier élément soit atteint.
Enfin, l'élément pivot est échangé avec le deuxième pointeur.
Permuter l'élément pivot avec le deuxième pointeur - Maintenant, les sous-parties gauche et droite de cet élément pivot sont prises pour un traitement ultérieur dans les étapes ci-dessous.
- Les éléments de pivot sont à nouveau choisis séparément pour les sous-parties gauche et droite. Dans ces sous-parties, les éléments de pivot sont placés à leur bonne position. Ensuite, l'étape 2 est répétée.
Sélectionnez l'élément pivot de dans chaque moitié et placez-le au bon endroit en utilisant la récursivité - Les sous-parties sont à nouveau divisées en sous-parties plus petites jusqu'à ce que chaque sous-partie soit formée d'un seul élément.
- À ce stade, le tableau est déjà trié.
Quicksort utilise la récursivité pour trier les sous-parties.
Sur la base de l'approche Divide and conquer, l'algorithme de tri rapide peut être expliqué comme suit:
- Divide
Le tableau est divisé en sous-parties prenant pivot comme point de partitionnement. Les éléments plus petits que le pivot sont placés à gauche du pivot et les éléments plus grands que le pivot sont placés à droite. - Conquérir
Les sous-parties gauche et droite sont à nouveau partitionnées à l'aide de en sélectionnant des éléments de pivot pour elles. Ceci peut être réalisé en passant récursivement les sous-parties dans l'algorithme. - Combiner
Cette étape ne joue pas un rôle significatif dans le tri rapide. Le tableau est déjà trié à la fin de l'étape de conquête.
Vous pouvez comprendre le fonctionnement du tri rapide à l'aide des illustrations ci-dessous.
Tri des éléments à gauche du pivot en utilisant la récursivité 
Tri des éléments à droite du pivot en utilisant la récursivité
Algorithme de tri rapide
quickSort (array, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- partition (array, leftmostIndex, rightmostIndex) quickSort (array, leftmostIndex, pivotIndex) quickSort (array, pivotIndex + 1, rightmostIndexIndex) partition, array, plus à gaucheIndexIndex ) set rightmostIndex comme pivotIndex storeIndex <- leftmostIndex - 1 for i <- leftmostIndex + 1 to rightmostIndex if element (i) <pivotElement swap element (i) and element (storeIndex) storeIndex ++ swap pivotElement and element (storeIndex + 1) return storeIndex + 1
Exemples Python, Java et 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); )
Complexité du tri rapide
Complexités temporelles
-
Pire complexité des cas (Big-O) : Cela se produit lorsque l'élément pivot choisi est le plus grand ou le plus petit élément. Cette condition conduit au cas où l'élément pivot se trouve dans une extrémité extrême du tableau trié. Un sous-tableau est toujours vide et un autre sous-tableau contient des éléments. Ainsi, quicksort n'est appelé que sur ce sous-tableau. Cependant, l'algorithme de tri rapide offre de meilleures performances pour les pivots dispersés.
O(n2)n - 1 - Meilleure complexité des cas (Big-omega) :
O(n*log n)
Cela se produit lorsque l'élément pivot est toujours l'élément du milieu ou près de l'élément du milieu. - Complexité moyenne des cas (Big-thêta) :
O(n*log n)
Cela se produit lorsque les conditions ci-dessus ne se produisent pas.
Complexité spatiale
La complexité de l'espace pour le tri rapide est O(log n).
Applications de tri rapide
Quicksort est mis en œuvre lorsque
- le langage de programmation est bon pour la récursivité
- la complexité du temps compte
- la complexité de l'espace compte
