Algorithme de tri en C
Tri à bulles
Le tri à bulles (Bubble Sort) est un algorithme de tri simple. Il parcourt de façon répétée la liste à trier, en comparant deux éléments à la fois, et les échange s'ils sont dans le mauvais ordre (par exemple du plus grand au plus petit, ou de la première lettre de A à Z).
Démonstration du processus :
Exemple
#include <stdio.h>
// Déclaration de fonction
void bubble_sort(int arr[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // Calculer la longueur du tableau
bubble_sort(arr, len); // Appeler la fonction de tri à bulles
// Afficher le tableau trié
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// Fonction de tri à bulles
void bubble_sort(int arr[], int len) {
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - 1 - i; j++) {
// Échanger les positions des éléments
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
Tri par sélection
Le tri par sélection est un algorithme de tri simple et intuitif. Son principe de fonctionnement est le suivant. Tout d'abord, trouvez le plus petit (ou le plus grand) élément dans la séquence non triée et placez-le au début de la séquence triée. Ensuite, continuez à trouver le plus petit (ou le plus grand) élément parmi les éléments non triés restants et placez-le à la fin de la séquence triée. Et ainsi de suite, jusqu'à ce que tous les éléments soient triés.
Démonstration du processus :
Exemple
#include <stdio.h>
// Déclaration de fonction
void selection_sort(int a[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // Calculer la longueur du tableau
selection_sort(arr, len); // Appeler la fonction de tri par sélection
// Afficher le tableau trié
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// Fonction de tri par sélection
void selection_sort(int a[], int len) {
for (int i = 0; i < len - 1; i++) {
int min = i; // Enregistrer la position de la valeur minimale ; le premier élément est le minimum par défaut.
for (int j = i + 1; j < len; j++) {
if (a[j] < a[min]) { // Trouver le minimum actuel
min = j; // Enregistrer la position de la valeur minimale
}
}
// Échanger deux variables
if (min != i) {
int temp = a[min];
a[min] = a[i];
a[i] = temp;
}
}
}
/*// Fonction d'échange personnalisée
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}*/
Tri par insertion
Tri par insertion (anglais : Insertion Sort) est un algorithme de tri simple et intuitif. Son principe de fonctionnement consiste à construire une séquence ordonnée. Pour les données non triées, parcourir de l'arrière vers l'avant la séquence triée, trouver la position appropriée et l'insérer. Dans la mise en œuvre, le tri par insertion adopte généralement un tri en place (c'est-à-dire un tri qui ne nécessite que {\displaystyle O(1)} {\displaystyle O(1)} d'espace supplémentaire). Par conséquent, lors du processus de balayage de l'arrière vers l'avant, il est nécessaire de déplacer de manière répétée les éléments triés vers l'arrière, étape par étape.
Décaler pour faire de la place au nouvel élément.Démonstration du processus :
Exemple
#include <stdio.h>
// Déclaration de fonction
void insertion_sort(int arr[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // Calculer la longueur du tableau
insertion_sort(arr, len); // Appeler la fonction de tri par insertion
// Afficher le tableau trié
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// Fonction de tri par insertion
void insertion_sort(int arr[], int len) {
for (int i = 1; i < len; i++) {
int temp = arr[i]; // Élément actuel à insérer
int j = i;
// Déplacer les éléments supérieurs à temp vers la droite
while (j > 0 && arr[j - 1] > temp) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = temp; // Insérer l'élément à la bonne position
}
}
Tri de Shell
Le tri de Shell, également appelé algorithme de tri par incréments décroissants, est une version améliorée plus efficace du tri par insertion. Le tri de Shell est un algorithme de tri instable.
Le tri de Shell propose des améliorations basées sur les deux propriétés suivantes du tri par insertion :
- Le tri par insertion est très efficace lorsqu'il opère sur des données presque déjà triées, et peut atteindre l'efficacité d'un tri linéaire.
- Mais le tri par insertion est généralement inefficace, car le tri par insertion ne peut déplacer les données que d'une position à la fois.
Démonstration du processus :
Exemple
#include <stdio.h>
// Déclaration de fonction
void shell_sort(int arr[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // Calculer la longueur du tableau
shell_sort(arr, len); // Appeler la fonction de tri de Shell
// Afficher le tableau trié
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// Fonction de tri de Shell
void shell_sort(int arr[], int len) {
// Calculer l'écart initial
for (int gap = len / 2; gap > 0; gap /= 2) {
// Effectuer un tri par insertion pour chaque écart
for (int i = gap; i < len; i++) {
int temp = arr[i]; // Élément actuel à insérer
int j = i;
// Déplacer les éléments supérieurs à temp
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp; // Insérer l'élément à la bonne position
}
}
}
Tri par fusion
Diviser les données en deux segments, puis à partir des deux segments sélectionner un par un le plus petit élément et le déplacer à la fin du nouveau segment de données.
Peut être effectué de haut en bas ou de bas en haut.
Démonstration du processus :
Méthode itérative
#include <stdio.h>
#include <stdlib.h>
// Déclaration de fonction
int min(int x, int y);
void merge_sort(int arr[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // Calculer la longueur du tableau
merge_sort(arr, len); // Appeler la fonction de tri par fusion
// Afficher le tableau trié
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// Retourner le minimum de deux nombres
int min(int x, int y) {
return x < y ? x : y;
}
// Fonction de tri par fusion
void merge_sort(int arr[], int len) {
int* a = arr;
int* b = (int*) malloc(len * sizeof(int));
if (b == NULL) { // Vérifier si l'allocation de mémoire a réussi
fprintf(stderr, "L'allocation de mémoire a échoué\n");
exit(EXIT_FAILURE);
}
for (int seg = 1; seg < len; seg += seg) {
for (int start = 0; start < len; start += seg + seg) {
int low = start;
int mid = min(start + seg, len);
int high = min(start + seg + seg, len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
// Fusionner deux sous-tableaux
while (start1 < end1 && start2 < end2) {
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
}
while (start1 < end1) {
b[k++] = a[start1++];
}
while (start2 < end2) {
b[k++] = a[start2++];
}
}
// Échanger les pointeurs de tableau
int* temp = a;
a = b;
b = temp;
}
// Si a et arr sont différents, recopier le contenu de a dans arr
if (a != arr) {
for (int i = 0; i < len; i++) {
b[i] = a[i];
}
b = a;
}
free(b); // libérer la mémoire
}
Méthode récursive
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Déclaration de fonction
void merge_sort_recursive(int arr[], int reg[], int start, int end);
void merge_sort(int arr[], const int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // Calculer la longueur du tableau
merge_sort(arr, len); // Appeler la fonction de tri par fusion
// Afficher le tableau trié
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// Implémenter récursivement le tri fusion
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
if (start >= end)
return;
int mid = start + (end - start) / 2;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2) {
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
}
while (start1 <= end1) {
reg[k++] = arr[start1++];
}
while (start2 <= end2) {
reg[k++] = arr[start2++];
}
// Utiliser memcpy pour copier les tableaux afin d'améliorer l'efficacité
memcpy(arr + start, reg + start, (end - start + 1) * sizeof(int));
}
// Fonction d'entrée pour le tri fusion
void merge_sort(int arr[], const int len) {
int* reg = (int*)malloc(len * sizeof(int));
if (reg == NULL) { // Vérifier si l'allocation de mémoire a réussi
fprintf(stderr, "L'allocation de mémoire a échoué\n");
exit(EXIT_FAILURE);
}
merge_sort_recursive(arr, reg, 0, len - 1);
free(reg); // libérer la mémoire
}
Tri rapide
Choisissez aléatoirement un élément dans l'intervalle comme pivot, placez les éléments plus petits que le pivot avant le pivot, et les éléments plus grands que le pivot après le pivot, puis triez séparément la zone des petits éléments et la zone des grands éléments.
Démonstration du processus :
Méthode itérative
#include <stdio.h>
// Structure Range
typedef struct _Range {
int start, end;
} Range;
// Créer une nouvelle plage
Range new_Range(int s, int e) {
Range r;
r.start = s;
r.end = e;
return r;
}
// Échange deux entiers
void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
// Fonction de tri rapide
void quick_sort(int arr[], const int len) {
if (len <= 0)
return; // Éviter une erreur de segmentation lorsque len est négatif
Range r[len];
int p = 0;
r[p++] = new_Range(0, len - 1);
while (p > 0) {
Range range = r[--p];
if (range.start >= range.end)
continue;
int mid = arr[(range.start + range.end) / 2]; // Sélectionner le point milieu comme pivot
int left = range.start, right = range.end;
do {
while (arr[left] < mid) ++left; // Vérifier si le côté gauche du pivot répond aux exigences
while (arr[right] > mid) --right; // Vérifier si le côté droit du pivot répond aux exigences
if (left <= right) {
swap(&arr[left], &arr[right]);
left++;
right--; // Déplacer les pointeurs pour continuer
}
} while (left <= right);
if (range.start < right) r[p++] = new_Range(range.start, right);
if (range.end > left) r[p++] = new_Range(left, range.end);
}
}
int main() {
int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
int len = sizeof(arr) / sizeof(arr[0]); // Calculer la longueur du tableau
quick_sort(arr, len); // Appeler la fonction de tri rapide
// Afficher le tableau trié
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Méthode récursive
#include <stdio.h>
// Échanger deux entiers
void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
// Implémentation récursive du tri rapide
void quick_sort_recursive(int arr[], int start, int end) {
if (start >= end)
return;
int mid = arr[end];
int left = start, right = end - 1;
while (left < right) {
while (left < right && arr[left] < mid)
left++;
while (left < right && arr[right] >= mid)
right--;
swap(&arr[left], &arr[right]);
}
if (arr[left] >= arr[end])
swap(&arr[left], &arr[end]);
else
left++;
quick_sort_recursive(arr, start, left - 1);
quick_sort_recursive(arr, left + 1, end);
}
// Fonction d'entrée du tri rapide
void quick_sort(int arr[], int len) {
quick_sort_recursive(arr, 0, len - 1);
}
int main() {
int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
int len = sizeof(arr) / sizeof(arr[0]); // Calculer la longueur du tableau
quick_sort(arr, len); // Appeler la fonction de tri rapide
// Afficher le tableau trié
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}