Bubble méthode c inférence sérielle. Tri à bulles et tout, tout, tout. Amélioration de l'algorithme de tri à bulles Pascal

Organisons le tableau de haut en bas, du zéro élément au dernier.

L'idée de la méthode : l'étape de tri consiste à parcourir de bas en haut le tableau. Des paires d'éléments voisins sont vues le long du chemin. Si les éléments d'une paire sont dans le mauvais ordre, alors nous les échangeons.

Après le passage du zéro à travers le tableau, le "top" est l'élément "le plus léger" - d'où l'analogie avec une bulle. La passe suivante est effectuée vers le deuxième élément par le haut, de sorte que le deuxième plus grand élément est levé à la bonne position ...

Nous effectuons des passes le long de la partie inférieure de plus en plus décroissante du tableau jusqu'à ce qu'il ne reste plus qu'un élément. Ceci termine le tri, puisque la séquence est dans l'ordre croissant.

Modèle void bubbleSort (T a, taille longue) (long i, j; T x; for (i = 0; i< size; i++) { // i - numéro de passe pour (j = taille-1; j> i; j--) ( // boucle interne de la passe si (a> a [j]) (x = a; a = a [j]; a [j] = x;))))

Le nombre moyen de comparaisons et d'échanges a un ordre de croissance quadratique : Theta (n 2), d'où l'on peut conclure que l'algorithme à bulles est très lent et inefficace.
Néanmoins, il a un énorme plus : il est simple et peut être amélioré de n'importe quelle manière. Ce que nous allons faire maintenant.

Considérons d'abord la situation où aucun échange n'a eu lieu sur aucune des allées. Qu'est-ce que ça veut dire?

Cela signifie que toutes les paires sont dans le bon ordre, donc le tableau est déjà trié. Et cela n'a aucun sens de continuer le processus (surtout si le tableau a été trié dès le début !).

Ainsi, la première amélioration de l'algorithme est de se rappeler si un échange a été effectué sur un passage donné. Sinon, l'algorithme se termine.

Le processus d'amélioration peut être poursuivi si vous vous souvenez non seulement du fait de l'échange lui-même, mais également de l'indice du dernier échange k. En effet : toutes les paires d'éléments voisins d'indices inférieurs à k sont déjà dans l'ordre requis. D'autres passes peuvent se terminer à l'indice k, au lieu de passer à une limite supérieure prédéterminée i.

Une amélioration qualitativement différente de l'algorithme peut être obtenue à partir de l'observation suivante. Bien que la bulle légère du bas monte vers le haut en un seul passage, les bulles lourdes descendent à la vitesse minimale : un pas par itération. Ainsi, le tableau 2 3 4 5 6 1 sera trié en 1 passage, et le tri de la séquence 6 1 2 3 4 5 prendra 5 passages.

Pour éviter cet effet, vous pouvez changer le sens des passes successives. L'algorithme résultant est parfois appelé " shaker-tri".

Modèle void shakerSort (T a, taille longue) (long j, k = taille-1 ; long lb = 1, ub = taille-1 ; // bornes de la partie non triée du tableau Tx; faire ( // passe de bas en haut pour (j = ub; j> 0; j--) (si (a> a [j]) (x = a; a = a [j]; a [j] = x; k = j;)) lb = k + 1; // passe de haut en bas pour (j = 1; j<=ub; j++) { if (a >a [j]) (x = a; a = a [j]; a [j] = x; k = j;)) ub = k-1; ) tandis que (lb< ub); }

Dans quelle mesure les changements décrits ont-ils affecté l'efficacité de la méthode ? Le nombre moyen de comparaisons, bien que diminué, reste O (n 2), alors que le nombre d'échanges n'a pas du tout changé. Le nombre moyen (c'est le pire) d'opérations reste quadratique.

De la mémoire supplémentaire n'est évidemment pas nécessaire. Le comportement de la méthode améliorée (mais pas initiale) est assez naturel, un tableau presque trié sera trié beaucoup plus rapidement qu'un tableau aléatoire. Le tri à bulles est stable, mais l'agitateur de tri perd cette qualité.

En pratique, la méthode des bulles, même avec des améliorations, est hélas trop lente. Par conséquent, il n'est presque jamais utilisé.

Méthode de la bulle

Tri échanges simples , tri à bulles(eng. tri à bulles) est un algorithme de tri simple. Pour la compréhension et la mise en œuvre, cet algorithme est le plus simple, mais il n'est efficace que pour les petits tableaux. Complexité de l'algorithme : O ( m²).

L'algorithme est considéré comme pédagogique et n'est pratiquement pas utilisé en dehors de la littérature pédagogique, mais en pratique, le tri par insertions est utilisé.

Algorithme

Un exemple de bulle triant une liste de nombres aléatoires.

L'algorithme consiste en des passages répétés dans le tableau à trier. Pour chaque passe, les éléments sont comparés séquentiellement par paires, et si l'ordre dans la paire est incorrect, les éléments sont échangés. Les passages dans le tableau sont répétés jusqu'à ce qu'au passage suivant, il s'avère que les échanges ne sont plus nécessaires, ce qui signifie que le tableau est trié. Lors du passage de l'algorithme, un élément déporté "flotte" jusqu'à la position souhaitée comme une bulle dans l'eau, d'où le nom de l'algorithme.

Parfois, à chaque étape, le tableau est vu du début, puis de la fin. C'est ce qu'on appelle le classement par shaker.

Exemples de mise en œuvre

Python

Def swap (arr, i, j): arr [i], arr [j] = arr [j], arr [i] def bubble_sort (arr): i = len (arr) tandis que i> 1 : pour j dans xrange (i - 1) : si arr [j]> arr [j + 1] : échanger (arr, j, j + 1) i - = 1

VBA

Sous-tri (Mus () As Long) Dim n As Long, i As Long, tmp As Long i = 1 Do While (i< UBound (Mus) ) If Mus(i) >Mus (i + 1) Then tmp = Mus (i) Mus (i) = Mus (i + 1) Mus (i + 1) = tmp If i> 1 Then i = i - 1 Else i = i + 1 End If Sinon i = i + 1 End If Loop End Sub

Amélioration de l'algorithme de tri à bulles Pascal

P : = vrai ; (Il y a une permutation) K : = 1 ; (Voir le numéro) Tant que P Do Begin P: = false; Pour i: = 1 To n-k Do Si X [i]> X [i + 1] Alors Begin A: = X [i]; X [i] : = X [i + 1] ; X [i + 1] : = A ; P : = vrai ; Finir; k : = k + 1 ; Finir;

PHP

$ taille = nombre ($ arr) -1 ; pour ($ i = $ taille; $ i> = 0; $ i -) (pour ($ j = 0; $ j<=($i -1 ) ; $j ++) if ($arr [ $j ] >$ arr [$ j +1]) ($ k = $ arr [$ j]; $ arr [$ j] = $ arr [$ j +1]; $ arr [$ j +1] = $ k;))

Non seulement elle n'est pas considérée comme la méthode la plus rapide, de plus, elle ferme la liste des méthodes de commande les plus lentes. Cependant, il a aussi ses avantages. Ainsi, le tri par la méthode des bulles est la solution la plus logique et la plus naturelle au problème, si vous devez organiser les éléments dans un certain ordre. Une personne ordinaire, par exemple, l'utilisera manuellement - juste par intuition.

D'où vient ce nom inhabituel ?

Le nom de la méthode a été inventé en utilisant une analogie avec les bulles d'air dans l'eau. Ceci est une métaphore. Tout comme les petites bulles d'air montent vers le haut - après tout, leur densité est supérieure à celle de n'importe quel liquide (dans ce cas, de l'eau), de sorte que chaque élément du réseau, plus sa valeur est petite, plus il se dirige progressivement vers le début de la liste des nombres.

Description de l'algorithme

Le tri par bulles se fait comme suit :

premier passage : les éléments du tableau de nombres sont pris par deux et sont également comparés deux à deux. Si dans quelques deux éléments la première valeur s'avère supérieure à la seconde, le programme échange leurs places ;
par conséquent, il se termine à la fin du tableau. Alors que tous les autres éléments restent, pour ainsi dire, dans un ordre chaotique et nécessitent toujours un tri;
par conséquent, la deuxième passe est nécessaire: elle est faite par analogie avec la précédente (déjà décrite) et a le nombre de comparaisons - moins une;
la passe numéro trois a une comparaison de moins que la seconde et deux de moins que la première. Etc;
pour résumer, chaque passe a (valeurs totales dans le tableau, un nombre spécifique) moins (numéro de passe) comparaisons.

Encore plus court, l'algorithme du futur programme peut s'écrire comme suit :

un tableau de nombres est vérifié jusqu'à ce que deux nombres soient trouvés, et le second d'entre eux doit être supérieur au premier ;
le programme échange les éléments du tableau mal situés les uns par rapport aux autres.

Pseudocode basé sur l'algorithme décrit

La mise en œuvre la plus simple est la suivante :

Procédure Sortirovka_Puzirkom;

Début

cycle pour j de nachalnii_index avant konechii_index;

cycle pour je de nachalnii_index avant konechii_index-1;

si massiv [i]> massiv

(changer les valeurs par endroits);

Finir

Bien entendu, la simplicité ici ne fait qu'aggraver la situation : plus l'algorithme est simple, plus toutes les lacunes y apparaissent. Le coût du temps est trop élevé même pour un petit tableau (ici la relativité entre en jeu : pour un profane, le temps peut sembler petit, mais dans le métier d'un programmeur, chaque seconde ou même une milliseconde compte).

Une meilleure mise en œuvre s'imposait. Par exemple, en tenant compte de l'échange de valeurs dans le tableau par lieux :

Procédure Sortirovka_Puzirkom;

Début

sortirovka = vrai ;

vélo au revoir sortirovka = vrai ;

sortirovka = faux ;

cycle pour je de nachalnii_index avant konechii_index-1;

si massiv [i]> massiv(le premier élément est supérieur au second), alors :

(on échange les éléments par endroits) ;

sortirovka = vrai ; (indiquait que l'échange avait été effectué).

Finir.

Inconvénients de la méthode

Le principal inconvénient est la durée du processus. Combien de temps dure la bulle ?

Le temps d'exécution est calculé à partir du carré du nombre de nombres dans le tableau - le résultat final lui est proportionnel.

Dans le pire des cas, le tableau sera parcouru autant de fois qu'il y a d'éléments moins une valeur. C'est parce qu'à la fin, il ne reste qu'un seul élément avec rien à comparer, et le dernier passage dans le tableau devient une action inutile.

De plus, la méthode de tri par échanges simples, comme on l'appelle aussi, n'est efficace que pour des tableaux de petite taille. Il ne sera pas possible de traiter de grandes quantités de données avec son aide: le résultat sera soit des erreurs, soit un échec du programme.

Dignité

Le tri à bulles est très facile à comprendre. Dans les programmes des universités techniques, lors de l'étude de l'ordre des éléments de tableau, c'est la première étape. La méthode est facilement implémentée comme dans le langage Programmation Delphi(D (Delphi) et C/C++ (C/C plus plus), un algorithme incroyablement simple pour organiser les valeurs dans le bon ordre et Bubble Sort est idéal pour les débutants.

En raison de lacunes, l'algorithme n'est pas utilisé à des fins parascolaires.

Principe de tri clair

Vue initiale du réseau 8 22 4 74 44 37 1 7

Étape 1 8 22 4 74 44 37 1 7

8 22 4 74 44 1 37 7

8 22 4 74 1 44 37 7

8 22 4 1 74 44 37 7

8 22 1 4 74 44 37 7

8 1 22 4 74 44 37 7

1 8 22 4 74 44 37 7

Étape 2 1 8 22 4 74 44 7 37

1 8 22 4 74 7 44 37

1 8 22 4 7 74 44 37

1 8 4 22 7 74 44 37

1 4 8 22 7 74 44 37

Étape 3 1 4 8 22 7 74 37 44

1 4 8 22 7 37 74 44

1 4 8 7 22 37 74 44

1 4 7 8 22 37 74 44

Étape 4 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Étape 5 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Étape 6 1 4 7 8 22 37 44 74

1 4 7 8 22 37 44 74

Étape 7 1 4 7 8 22 37 44 74

Exemple de tri à bulles en Pascal

Exemple:

const kol_mas = 10;

var massiv : tableau d'entiers ;

a, b, k : nombre entier ;

writeln ("entrée", kol_mas, "éléments du tableau");

pour a : = 1 à kol_mas do readln (massiv [a]) ;

pour a : = 1 à kol_mas-1 ne commence

pour b : = a + 1 à kol_mas ne commence

si massiv [a]> massiv [b] alors commencer

k : = massif [a] ; masseiv [a] : = masseiv [b] ; masseiv [b] : = k ;

finir;

writeln ("après tri");

pour a : = 1 à kol_mas do writeln (massiv [a]) ;

Un exemple de tri à bulles en C (C)

#comprendre

int main (int argc, char * argv)

int massiv = (36, 697, 73, 82, 68, 12, 183, 88), i, ff;

pour (;;) (

ff = 0 ;

pour (i = 7; i> 0; i -) (

si (massif [i]< massiv) {

échanger (massiv [i], massiv);

si (ff == 0) cassure ;

getch (); // délai d'écran

Mots clés: Trier par bulle si, si tri à bulles, tri par bulles d'un tableau à deux dimensions

Tri à bulles

Et l'algorithme est très simple. Nous parcourons le tableau de nombres et vérifions l'ordre (le nombre suivant doit être supérieur et égal au précédent), dès que nous rencontrons une violation de l'ordre, nous échangeons immédiatement les éléments, atteignons la fin du tableau , puis recommencez.

Trions le tableau (1, 5, 2, 7, 6, 3)
Nous parcourons le tableau, vérifions le premier nombre et le second, ils vont dans l'ordre croissant. Ensuite, il y a violation de l'ordre, nous échangeons ces éléments
1, 2, 5, 7, 6, 3
On continue à parcourir le tableau, 7 c'est plus que 5, mais 6 c'est moins, donc on échange des places
1, 2, 5, 6, 7, 3
3 en panne, échanger avec 7
1, 2, 5, 6, 3, 7
Revenez au début du tableau et faites de même.

1, 2, 5, 3, 6, 7
1, 2, 3, 5, 6, 7

Ils disent que cela est similaire à "l'émergence" d'éléments "plus légers", comme les bulles, c'est pourquoi l'algorithme tire son nom. void bubbleSort (int * a, size_t size) (size_t i, j; int tmp; for (i = 1; i< size; i++) { for (j = 1; j < size; j++) { if (a[j] >a) (tmp = a [j]; a [j] = a; a = tmp;))))

Cet algorithme prendra toujours (n-1) 2 étapes, quelle que soit l'entrée. Même si le tableau est trié, il sera toujours parcouru (n-1) 2 fois. De plus, les données déjà triées seront à nouveau vérifiées.

Supposons que vous ayez besoin de trier le tableau 1, 2, 4, 3

1 2 4 3
1 2 4 3
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4

Une fois les éléments a et a permutés, il n'est plus nécessaire de parcourir cette section du tableau. Prenons cela en compte et redessinons l'algorithme.

Void bubbleSort2 (int * a, size_t size) (size_t i, j; int tmp; for (i = 1; i< size; i++) { for (j = i; j >0 ; j--) (si (un [j]< a) { tmp = a[j]; a[j] = a; a = tmp; } } } }

Une autre implémentation

Void bubbleSort2b (int * a, size_t size) (size_t i, j; int tmp; for (i = 1; i< size; i++) { for (j = 1; j <= size-i; j++) { if (a[j] < a) { tmp = a[j]; a[j] = a; a = tmp; } } } }

Dans ce cas, il y aura déjà la moitié des étapes, mais il reste toujours le problème du tri d'un tableau déjà trié : vous devez faire en sorte que la fonction regarde une fois le tableau trié. Pour ce faire, nous introduisons une variable flag : elle sera omise (flag = 0) si le tableau est trié. Dès que nous tombons sur une panne, le drapeau sera levé (flag = 1) et nous commencerons à trier le tableau comme d'habitude.

Void bubbleSort3 (int * a, size_t size) (size_t i; int tmp; char flag; do (flag = 0; for (i = 1; i< size; i++) { if (a[i] < a) { tmp = a[i]; a[i] = a; a = tmp; flag = 1; } } } while (flag); }

Dans ce cas, la complexité est également de l'ordre de n 2, mais dans le cas d'un tableau trié, il n'y aura qu'une seule passe.

Améliorons maintenant l'algorithme. Écrivons une fonction générale pour trier un tableau de type void. Le type de la variable n'étant pas connu, il faudra en plus transférer la taille d'un élément du tableau et la fonction de comparaison.

Int intSort (const void * a, const void * b) (return * ((int *) a)> * ((int *) b);) void bubbleSort3g (void * a, size_t item, size_t size, int (* cmp) (const void *, const void *)) (size_t i; void * tmp = NULL; char flag; tmp = malloc (item); do (flag = 0; for (i = 1; i< size; i++) { if (cmp(((char*)a + i*item), ((char*)a + (i-1)*item))) { memcpy(tmp, ((char*)a + i*item), item); memcpy(((char*)a + i*item), ((char*)a + (i-1)*item), item); memcpy(((char*)a + (i-1)*item), tmp, item); flag = 1; } } } while (flag); free(tmp); }

La fonction a l'air moche - l'adresse de l'élément actuel et précédent est souvent calculée. Sélectionnons des variables distinctes pour cela.

Void bubbleSort3gi (void * a, size_t item, size_t size, int (* cmp) (const void *, const void *)) (size_t i; void * tmp = NULL; void * prev, * cur; char flag; tmp = malloc (item); do (flag = 0; i = 1; prev = (char *) a; cur = (char *) prev + item; while (i< size) { if (cmp(cur, prev)) { memcpy(tmp, prev, item); memcpy(prev, cur, item); memcpy(cur, tmp, item); flag = 1; } i++; prev = (char*)prev + item; cur = (char*)cur + item; } } while (flag); free(tmp); }

Maintenant, en utilisant ces fonctions, vous pouvez trier des tableaux de tout type, par exemple

Void principal () (int a = (1, 0, 9, 8, 7, 6, 2, 3, 4, 5) ; int i ; bubbleSort3gi (a, sizeof (int), 10, intSort) ; pour (i = 0 ; je< 10; i++) { printf("%d ", a[i]); } _getch(); }

Trier un tableau multidimensionnel

Le tri d'un tableau multidimensionnel statique est essentiellement le même que le tri d'un tableau unidimensionnel. Vous pouvez tirer parti de la propriété selon laquelle les tableaux statiques unidimensionnels et multidimensionnels ont la même représentation de la mémoire.

Void principal () (int a = (1, 9, 2, 8, 3, 7, 4, 6, 5) ; int i, j ; bubbleSort3gi (a, sizeof (int), 9, intSort) ; pour (i = 0 ; je< 3; i++) { for (j = 0; j < 3; j++) { printf("%d ", a[i][j]); } } } Сортировка динамически созданного двумерного массива может быть произведена двумя способами. Во-первых, можно по определённому алгоритму находить индекс i-го и j-го элемента по порядковому номеру k от 0 до n * m. #include #comprendre #comprendre #comprendre void bubbleSort2d (int ** a, size_t m, size_t n) (int tmp; size_t i, j, k, jp, ip; size_t size = m * n; char flag; do (flag = 0; for (k = 1 ;k< size; k++) { //Вычисляем индексы текущего элемента j = k / m; i = k - j*m; //Вычисляем индексы предыдущего элемента jp = (k-1) / m; ip = (k-1) - jp*m; if (a[i][j] >a) (tmp = a [i] [j]; a [i] [j] = a; a = tmp; flag = 1;))) while (flag); ) #define SIZE_X 3 #define SIZE_Y 4 void main () (int ** a = NULL; int i, j; a = (int **) malloc (sizeof (int *) * SIZE_X); for (i = 0; je< SIZE_X; i++) { a[i] = (int*) malloc(sizeof(int) * SIZE_Y); for (j = 0; j < SIZE_Y; j++) { a[i][j] = rand(); printf("%8d ", a[i][j]); } printf("\n"); } printf("\nafter sort\n"); bubbleSort2d(a, SIZE_X, SIZE_Y); for (i = 0; i < SIZE_X; i++) { for (j = 0; j < SIZE_Y; j++) { printf("%8d ", a[i][j]); } printf("\n"); } for (i = 0; i < SIZE_X; i++) { free(a[i]); } free(a); _getch(); }

Deuxièmement, vous pouvez d'abord déplacer le tableau à une dimension, trier le tableau à une dimension, puis le ramener à deux dimensions.

Void bubbleSort3gi2d (void ** a, size_t item, size_t m, size_t n, int (* cmp) (const void *, const void *)) (size_t size = m * n, sub_size = n * item; size_t i, j , k; void * arr = malloc (taille * élément); char * p1d = (char *) arr; char * p2d = (char *) a; // Copie un tableau à deux dimensions de type void en une dimension pour ( je = 0; je< m; i++) { memcpy(p1d + i*sub_size, *((void**)(p2d + i*item)), sub_size); } bubbleSort3gi(arr, item, size, cmp); //Копируем одномерный массив обратно в двумерный for (i = 0; i < m; i++) { memcpy(*((void**)(p2d + i*item)), p1d + i*sub_size, sub_size); } }

Si vous ne comprenez pas cette fonction, utilisez-en une dactylographiée. Appel, de l'exemple précédent

On a estimé que jusqu'à un quart du temps ordinateurs centralisés se concentre sur le tri des données. C'est parce qu'il est beaucoup plus facile de trouver une valeur dans un tableau qui a été trié au préalable. Sinon, chercher c'est un peu comme chercher une aiguille dans une botte de foin.

Il y a des programmeurs qui passent tout leur temps de travail à étudier et à mettre en œuvre des algorithmes de tri. En effet, la grande majorité des logiciels en entreprise implique la gestion de bases de données. Les gens recherchent des informations dans les bases de données tout le temps. Cela signifie que les algorithmes de recherche sont très demandés.

Mais il y a un "mais". Les algorithmes de recherche sont beaucoup plus rapides avec des bases de données déjà triées. Dans ce cas, seule une recherche linéaire est requise.

Alors que les ordinateurs sont sans utilisateurs à certains moments, les algorithmes de tri continuent de fonctionner avec les bases de données. Les utilisateurs en recherche reviennent et la base de données a déjà été triée en fonction d'un objectif de recherche particulier.

Cet article fournit des exemples d'implémentation d'algorithmes de tri standard.

Tri par sélection

Afin de trier le tableau dans l'ordre croissant, vous devez trouver l'élément avec la plus grande valeur à chaque itération. Avec lui, vous devez échanger le dernier élément. L'élément suivant avec la valeur la plus élevée est déjà à l'avant-dernière place. Cela devrait se produire jusqu'à ce que les éléments qui se trouvent aux premiers endroits du tableau soient dans le bon ordre.

code C++

void SortAlgo :: selectionSort (int data, int lenD) (int j = 0; int tmp = 0; for (int i = 0; i données [k]) (j = k;)) tmp = données [i]; données [i] = données [j] ; données [j] = tmp; ))

Tri à bulles

Le tri à bulles compare les éléments adjacents et permute si l'élément suivant est plus petit que le précédent. Nécessite plusieurs passages sur les données. Lors de la première passe, les deux premiers éléments du tableau sont appariés. S'ils sont en panne, ils sont permutés puis les éléments de la paire suivante sont comparés. Dans la même condition, ils changent aussi de place. Ainsi, le tri se produit à chaque cycle jusqu'à ce que la fin du tableau soit atteinte.

code C++

void SortAlgo :: bubbleSort (int data, int lenD) (int tmp = 0; for (int i = 0; i = (i + 1); j -) (si (données [j]

Tri par insertion

Le tri par insertion divise le tableau en deux régions : ordonné et et non ordonné. Le tableau entier est initialement une zone non ordonnée. Lors du premier passage, le premier article de la zone non commandée est retiré et placé dans la bonne position dans la zone commandée.

À chaque passage, la taille de la région ordonnée augmente de 1 et la taille de la région non ordonnée diminue de 1.

La boucle principale va de 1 à N-1. À la jième itération, [i] est inséré à la bonne position dans la région ordonnée. Cela se fait en décalant tous les éléments de la région ordonnée qui sont supérieurs à [i] d'une position vers la droite. [i] est inséré entre les éléments inférieurs à [i] et ceux supérieurs à [i].

code C++

void SortAlgo :: insertionSort (int data, int lenD) (int key = 0; int i = 0; for (int j = 1; j = 0 && data [i]> key) (data = data [i]; i = i-1; data = key;)))

Tri par fusion

code C++

void SortAlgo :: mergeSort (int data, int lenD) (if (lenD> 1) (int middle = lenD / 2; int rem = lenD-middle; int * L = new int; int * R = new int; for ( entier je = 0; je

Tri rapide

Quicksort utilise un algorithme diviser pour régner. Il commence par diviser le tableau d'origine en deux régions. Ces parties se trouvent à gauche et à droite de l'élément marqué, appelé pivot. À la fin du processus, une partie contiendra des éléments plus petits que le pivot et l'autre partie contiendra des éléments plus grands que le pivot.

code C++

void SortAlgo :: quickSort (int * data, int const len) (int const lenD = len; int pivot = 0; int ind = lenD / 2; int i, j = 0, k = 0; if (lenD> 1) (int * L = new int; int * R = new int; pivot = data; for (i = 0; i