introduction
Le tri d'un tableau est l'un des premiers problèmes sérieux étudiés dans le cours classique "Algorithmes et structures de données" de la discipline informatique. À cet égard, les tâches d'écriture des sortes et les questions correspondantes sont souvent rencontrées dans les entretiens en tant que stagiaire ou développeur junior.
Formulation du problème
Traditionnellement, il vaut la peine de commencer la présentation des solutions au problème avec son énoncé. Habituellement, la tâche de tri consiste à classer un tableau d'entiers dans l'ordre croissant. Mais en fait, c'est un peu une simplification excessive. Les algorithmes décrits dans cette section peuvent être utilisés pour ordonner un tableau de tous les objets entre lesquels une relation de classement est établie (c'est-à-dire que pour deux éléments quelconques, nous pouvons dire: le premier est supérieur au second, le second est supérieur au premier, ou ils sont égaux). Vous pouvez trier à la fois par ordre croissant et décroissant. Nous utiliserons la simplification standard.
Tri de sélection
L'un des types les plus simples est le tri par sélection.
Description de l'algorithme
Le tri d'un tableau par sélection est effectué comme suit: le tableau est divisé en deux parties. Une partie est appelée triée et l'autre non triée. L'algorithme suppose de parcourir le tableau entier de sorte que la longueur de la partie triée devienne égale à la longueur du tableau entier. Dans chaque itération, nous trouvons le minimum dans la partie non triée du tableau et échangeons ce minimum avec le premier élément de la partie non triée du tableau. Ensuite, nous augmentons la longueur de la partie triée du tableau de un. Un exemple d'une itération est présenté ci-dessous:
1 3 5 | 8 9 6 -> 1 3 5 6 | 9 8
la mise en oeuvre
Je suggère de regarder l'implémentation de cet algorithme en C:
void choiseSortFunction(double A[], size_t N)
{
for(size_t tmp_min_index = 0; tmp_min_index < N;
tmp_min_index++) {
//
for(size_t k = tmp_min_index + 1; k < N; k++) {
if (A[k] < A[tmp_min_index]) {
double min_value = A[k];
A[k] = A[tmp_min_index];
A[tmp_min_index] = min_value;
}
}
}
}
Une analyse
Je propose d'analyser cet algorithme. Le corps de la boucle interne lui-même prend O (1), c'est-à-dire qu'il ne dépend pas de la taille du tableau en cours de tri. Cela signifie que pour comprendre les asymptotiques de l'algorithme, il est nécessaire de compter combien de fois ce corps est exécuté. Lors de la première itération de la boucle externe, il y a (n - 1) itérations de la boucle interne. Lors de la deuxième itération de la boucle externe - (n - 2) itérations de la boucle interne. Poursuivant ce raisonnement, nous arrivons à ce qui suit:
Dans le processus de calculs, nous avons d'abord utilisé les propriétés de la notation O, puis la formule pour calculer la somme d'une progression arithmétique.
Pour l'ordre, il est également nécessaire d'estimer la mémoire supplémentaire nécessaire à l'exécution de l'algorithme. Tout est beaucoup plus simple ici: nous avons alloué de la mémoire uniquement pour les compteurs de boucles et une variable - un tampon, qui permet d'échanger 2 éléments de tableau. Par conséquent:
À la suite de l'analyse, nous sommes arrivés à la conclusion que la complexité temporelle de l'algorithme dépend de la taille du tableau d'entrée quadratiquement. Par conséquent, ce tri appartient à la classe des sortes quadratiques . Le résultat de l'analyse ne dépend pas du contenu du tableau: il est correct au mieux, au pire et en moyenne.
Il est également important de noter que le tri par sélection est robuste dans cette implémentation . Permettez-moi de vous rappeler que le tri s'appelle stable.si l'ordre des éléments égaux ne change pas lors de son exécution. Cette propriété n'est pas très importante pour une tâche éducative telle que le tri d'un tableau de nombres, mais si nous triions des objets plus complexes avec une relation de classement établie, cela pourrait être important. Nous pouvons envisager un exemple similaire la prochaine fois que nous parlerons de tri par base.
Tri par sélection recto-verso
L'optimisation de l'algorithme implémenté ci-dessus peut être d'un certain intérêt: en parcourant la partie non triée du tableau, vous pouvez rechercher le maximum en parallèle avec l'élément minimum. Ainsi, après l'itération, vous pouvez réduire la partie non triée du tableau non pas d'un, mais de deux. L'algorithme ne s'améliore pas de manière asymptotique, mais néanmoins, la vitesse de son exécution peut légèrement augmenter, le nombre de comparaisons double également.
Tri par sélection récursive
En guise d'exercice, vous pouvez essayer d'écrire un algorithme n'utilisant pas de boucle, mais utilisant la récursivité. En java, cela pourrait ressembler à ceci:
public static int findMin(int[] array, int index){
int min = index - 1;
if(index < array.length - 1) min = findMin(array, index + 1);
if(array[index] < array[min]) min = index;
return min;
}
public static void selectionSort(int[] array){
selectionSort(array, 0);
}
public static void selectionSort(int[] array, int left){
if (left < array.length - 1) {
swap(array, left, findMin(array, left));
selectionSort(array, left+1);
}
}
public static void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
Résultat
Nous avons examiné l'un des types quadratiques: le tri par sélection, examiné une implémentation stable utilisant une boucle, la récursivité, discuté de l'optimisation de l'algorithme par réduction bidirectionnelle de la partie non triée du tableau. Le tri est purement éducatif et n'a pas trouvé une large application dans la pratique.
Si vous souhaitez en savoir plus sur le cours, j'invite tout le monde à un webinaire gratuit, qui se tiendra le 10 juillet .