quick sort c with examples
Quicksort en C ++ avec illustration.
Quicksort est un algorithme de tri largement utilisé qui sélectionne un élément spécifique appelé «pivot» et partitionne le tableau ou la liste à trier en deux parties en fonction de ce pivot s0 que les éléments inférieurs au pivot sont à gauche de la liste et des éléments supérieur au pivot sont à droite de la liste.
Ainsi, la liste est divisée en deux sous-listes. Les sous-listes peuvent ne pas être nécessaires pour la même taille. Puis Quicksort s'appelle lui-même récursivement pour trier ces deux sous-listes.
=> Consultez le guide de formation Perfect C ++ ici.
Ce que vous apprendrez:
- introduction
- Algorithme général
- Pseudo code pour Quicksort
- Illustration
- Exemple C ++
- Exemple Java
- Analyse de complexité de l'algorithme de tri rapide
- Tri rapide à 3 voies
- Quicksort randomisé
- Tri rapide et tri par fusion
- Conclusion
- lecture recommandée
introduction
Quicksort fonctionne de manière efficace et plus rapide, même pour des tableaux ou des listes plus volumineux.
Dans ce didacticiel, nous explorerons plus en détail le fonctionnement de Quicksort ainsi que quelques exemples de programmation de l'algorithme de tri rapide.
En tant que valeur pivot, nous pouvons choisir la première, la dernière ou la valeur moyenne ou n'importe quelle valeur aléatoire. L'idée générale est qu'en fin de compte, la valeur du pivot est placée à sa bonne position dans le tableau en déplaçant les autres éléments du tableau vers la gauche ou la droite.
Algorithme général
L'algorithme général pour Quicksort est donné ci-dessous.
quicksort(A, low, high) begin Declare array A[N] to be sorted low = 1st element; high = last element; pivot if(low Jetons maintenant un coup d'œil au pseudocode de la technique Quicksort.
Pseudo code pour Quicksort
//pseudocode for quick sort main algorithm procedure quickSort(arr[], low, high) arr = list to be sorted low – first element of array high – last element of array begin if (low Le fonctionnement de l'algorithme de partitionnement est décrit ci-dessous à l'aide d'un exemple.
Dans cette illustration, nous prenons le dernier élément comme pivot. Nous pouvons voir que le tableau est successivement divisé autour de l'élément pivot jusqu'à ce que nous ayons un seul élément dans le tableau.
Nous présentons maintenant une illustration du tri rapide ci-dessous pour mieux comprendre le concept.
Illustration
Voyons une illustration de l'algorithme de tri rapide. Considérez le tableau suivant avec le dernier élément comme pivot. En outre, le premier élément est étiqueté faible et le dernier élément est élevé.
ripper dvd gratuit pour windows 8.1
À partir de l'illustration, nous pouvons voir que nous déplaçons les pointeurs haut et bas aux deux extrémités du tableau. Chaque fois que des points bas vers l'élément plus grand que le pivot et des points hauts vers l'élément plus petit que le pivot, nous échangeons les positions de ces éléments et faisons avancer les pointeurs bas et haut dans leurs directions respectives.
Ceci est fait jusqu'à ce que les pointeurs bas et haut se croisent. Une fois qu'ils se croisent, l'élément pivot est placé à sa bonne position et le réseau est divisé en deux. Ensuite, ces deux sous-tableaux sont triés indépendamment en utilisant le tri rapide de manière récursive.
Exemple C ++
Vous trouverez ci-dessous l'implémentation de l'algorithme Quicksort en C ++.
#include using namespace std; // Swap two elements - Utility function void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // partition the array using last element as pivot int partition (int arr[], int low, int high) { int pivot = arr[high]; // pivot int i = (low - 1); for (int j = low; j <= high- 1; j++) { //if current element is smaller than pivot, increment the low element //swap elements at i and j if (arr[j] <= pivot) { i++; // increment index of smaller element swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } //quicksort algorithm void quickSort(int arr[], int low, int high) { if (low < high) { //partition the array int pivot = partition(arr, low, high); //sort the sub arrays independently quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void displayArray(int arr[], int size) { int i; for (i=0; i < size; i++) cout< Production:
Tableau d'entrée
12 23 3 43 51 35 19 45
questions et réponses d'entrevue bootstrap pour les
Tableau trié avec tri rapide
3 12 19 23 35 43 45 51
Ici, nous avons quelques routines utilisées pour partitionner le tableau et appeler quicksort de manière récursive pour trier la partition, la fonction de tri rapide de base et les fonctions utilitaires pour afficher le contenu du tableau et échanger les deux éléments en conséquence.
Tout d'abord, nous appelons la fonction quicksort avec le tableau d'entrée. Dans la fonction de tri rapide, nous appelons la fonction de partition. Dans la fonction de partition, nous utilisons le dernier élément comme élément pivot du tableau. Une fois le pivot décidé, le tableau est partitionné en deux parties, puis la fonction de tri rapide est appelée pour trier indépendamment les deux sous-tableaux.
Lorsque la fonction de tri rapide revient, le tableau est trié de telle sorte que l'élément pivot soit à son emplacement correct et que les éléments inférieurs au pivot soient à gauche du pivot et les éléments supérieurs au pivot se trouvent à droite du pivot.
Ensuite, nous implémenterons l'algorithme de tri rapide en Java.
Exemple Java
// Quicksort implementation in Java class QuickSort { //partition the array with last element as pivot int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low-1); // index of smaller element for (int j=low; j Production:
Tableau d'entrée
12 23 3 43 51 35 19 45
Tableau après le tri avec tri rapide
3 12 19 23 35 43 45 51
Dans l'implémentation Java également, nous avons utilisé la même logique que celle utilisée dans l'implémentation C ++. Nous avons utilisé le dernier élément du tableau comme pivot et tri rapide sur le tableau afin de placer l'élément pivot à sa bonne position.
Analyse de complexité de l'algorithme de tri rapide
Le temps nécessaire au tri rapide pour trier un tableau dépend du tableau d'entrée et de la stratégie ou de la méthode de partition.
Si k est le nombre d'éléments inférieur au pivot et n est le nombre total d'éléments, alors le temps général pris par le tri rapide peut être exprimé comme suit:
T (n) = T (k) + T (n-k-1) + O (n)
Ici, T (k) et T (n-k-1) sont le temps pris par les appels récursifs et O (n) est le temps pris par l'appel de partitionnement.
Analysons en détail cette complexité temporelle pour le tri rapide.
# 1) Le pire des cas : Le pire des cas dans la technique de tri rapide se produit principalement lorsque nous sélectionnons l'élément le plus bas ou le plus élevé du tableau comme pivot. (Dans l'illustration ci-dessus, nous avons sélectionné l'élément le plus élevé comme pivot). Dans une telle situation, le pire des cas se produit lorsque le tableau à trier est déjà trié par ordre croissant ou décroissant.
D'où l'expression ci-dessus pour le temps total pris change comme suit:
T (n) = T (0) + T (n-1) + O (n) qui se résout à Surdeux)
# 2) Meilleur cas: Le meilleur cas pour le tri rapide se produit toujours lorsque l'élément pivot sélectionné est au milieu du tableau.
Ainsi, la récurrence pour le meilleur des cas est:
questions d'entrevue sur le savon et le repos
T (n) = 2T (n / 2) + O (n) = O (nlogn)
# 3) Cas moyen: Pour analyser le cas moyen du tri rapide, nous devons considérer toutes les permutations de tableau, puis calculer le temps pris par chacune de ces permutations. En un mot, le temps moyen de tri rapide devient également O (nlogn).
Voici les diverses complexités de la technique Quicksort:
Pire complexité temporelle des cas O (n 2) stabilité Non stable car deux éléments avec les mêmes valeurs ne seront pas placés dans le même ordre. Stable - deux éléments avec les mêmes valeurs apparaîtront dans le même ordre dans la sortie triée. Meilleure complexité temporelle O (n * log n) Complexité temporelle moyenne O (n * log n) Complexité spatiale O (n * log n)
Nous pouvons implémenter le tri rapide de différentes manières simplement en changeant le choix de l'élément pivot (milieu, premier ou dernier), cependant, le pire des cas se produit rarement pour le tri rapide.
Tri rapide à 3 voies
Dans la technique originale de tri rapide, nous sélectionnons généralement un élément de pivot, puis divisons le tableau en sous-tableaux autour de ce pivot afin qu'un sous-tableau se compose d'éléments inférieurs au pivot et un autre se compose d'éléments plus grands que le pivot.
Mais que se passe-t-il si nous sélectionnons un élément pivot et qu'il y a plus d'un élément dans le tableau qui est égal à pivot?
Par exemple, considérons le tableau suivant {5,76,23,65,4,4,5,4,1,1,2,2,2,2}. Si nous effectuons un simple tri rapide sur ce tableau et sélectionnons 4 comme élément pivot, alors nous corrigerons une seule occurrence de l'élément 4 et le reste sera partitionné avec les autres éléments.
Au lieu de cela, si nous utilisons un tri rapide à 3 voies, nous diviserons le tableau [l… r] en trois sous-tableaux comme suit:
- Array [l… i] - Ici, i est le pivot et ce tableau contient des éléments inférieurs au pivot.
- Array [i + 1… j-1] - Contient les éléments qui sont égaux au pivot.
- Array [j… r] - Contient des éléments plus grands que le pivot.
Ainsi, le tri rapide à 3 voies peut être utilisé lorsque nous avons plus d'un élément redondant dans le tableau.
Quicksort randomisé
La technique de tri rapide est appelée technique de tri rapide aléatoire lorsque nous utilisons des nombres aléatoires pour sélectionner l'élément pivot. Dans le tri rapide aléatoire, il est appelé «pivot central» et divise le tableau de telle sorte que chaque côté comporte au moins ¼ d'éléments.
Le pseudo-code pour le tri rapide aléatoire est donné ci-dessous:
// Sorts an array arr[low..high] using randomized quick sort randomQuickSort(array[], low, high) array – array to be sorted low – lowest element in array high – highest element in array begin 1. If low >= high, then EXIT. //select central pivot 2. While pivot 'pi' is not a Central Pivot. (i) Choose uniformly at random a number from [low..high]. Let pi be the randomly picked number. (ii) Count elements in array[low..high] that are smaller than array[pi]. Let this count be a_low. (iii) Count elements in array[low..high] that are greater than array[pi]. Let this count be a_high. (iv) Let n = (high-low+1). If a_low >= n/4 and a_high >= n/4, then pi is a central pivot. //partition the array 3. Partition array[low..high] around the pivot pi. 4. // sort first half randomQuickSort(array, low, a_low-1) 5. // sort second half randomQuickSort(array, high-a_high+1, high) end procedure
Dans le code ci-dessus sur «randomQuickSort», à l'étape 2, nous sélectionnons le pivot central. A l'étape 2, la probabilité que l'élément sélectionné soit le pivot central est de 1/2. Par conséquent, la boucle de l'étape 2 devrait s'exécuter 2 fois. Ainsi, la complexité temporelle de l'étape 2 du tri rapide aléatoire est O (n).
L'utilisation d'une boucle pour sélectionner le pivot central n'est pas le moyen idéal d'implémenter un tri rapide aléatoire. Au lieu de cela, nous pouvons sélectionner au hasard un élément et l'appeler pivot central ou remanier les éléments du tableau. La complexité temporelle attendue dans le pire des cas pour l'algorithme de tri rapide aléatoire est O (nlogn).
Tri rapide et tri par fusion
Dans cette section, nous aborderons les principales différences entre le tri rapide et le tri par fusion.
Paramètre de comparaison Tri rapide Tri par fusion partitionnement Le tableau est partitionné autour d'un élément pivot et n'est pas nécessairement toujours en deux moitiés. Il peut être partitionné dans n'importe quel rapport. Le tableau est partitionné en deux moitiés (n / 2). Pire complexité des cas O (n 2) - de nombreuses comparaisons sont nécessaires dans le pire des cas. O (nlogn) - identique au cas moyen Utilisation des ensembles de données Ne fonctionne pas correctement avec des ensembles de données plus volumineux. Fonctionne bien avec tous les ensembles de données, quelle que soit leur taille. Espace supplémentaire En place - n'a pas besoin d'espace supplémentaire. Non en place - nécessite un espace supplémentaire pour stocker la matrice auxiliaire. Méthode de tri Interne - les données sont triées dans la mémoire principale. Externe - utilise la mémoire externe pour stocker les tableaux de données. Efficacité Plus rapide et efficace pour les listes de petite taille. Rapide et efficace pour les listes plus volumineuses. Tableaux / listes liées Plus préféré pour les tableaux. Fonctionne bien pour les listes liées.
Conclusion
Comme son nom l'indique, quicksort est l'algorithme qui trie la liste plus rapidement que tout autre algorithme de tri. Tout comme le tri par fusion, le tri rapide adopte également une stratégie de division et de conquête.
Comme nous l'avons déjà vu, en utilisant le tri rapide, nous divisons la liste en sous-tableaux en utilisant l'élément pivot. Ensuite, ces sous-tableaux sont triés indépendamment. À la fin de l'algorithme, le tableau entier est complètement trié.
Quicksort est plus rapide et fonctionne efficacement pour trier les structures de données. Quicksort est un algorithme de tri populaire et est parfois même préféré à l'algorithme de tri par fusion.
Dans notre prochain tutoriel, nous discuterons plus en détail du tri Shell.
=> Regardez la série de formations C ++ simple ici.
lecture recommandée
- Méthode MongoDB Sort () avec exemples
- Commande de tri Unix avec syntaxe, options et exemples
- Fusionner le tri en C ++ avec des exemples
- Tri de tas en C ++ avec des exemples
- Shell tri en C ++ avec des exemples
- Sélection de tri en C ++ avec des exemples
- Tri à bulles en C ++ avec des exemples
- Tri par insertion en C ++ avec des exemples