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, 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.
Trier par insertions
La dernière fois, nous avons parlé de l'un des types les plus simples: le tri par sélection . Aujourd'hui, nous allons nous concentrer sur un algorithme un peu plus complexe - le tri par insertion.
Description de l'algorithme
Le tri d'un tableau par insertions se fait de la façon suivante: tout comme dans le cas du tri par sélection, 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 prenons le premier élément de la partie non triée du tableau et effectuons l'opération suivante avec lui: alors que notre élément est strictement inférieur au précédent, nous les échangeons. Ensuite, nous augmentons la longueur de la partie triée du tableau de un. Ainsi, en déplaçant successivement l'élément étudié, on parvient à ce qu'il se mette en place. Un exemple d'une itération est présenté ci-dessous:
1 3 5 | 2 9 6 -> 1 3 2 5 9 6 -> 1 2 3 5 9 6 -> 1 2 3 5 | 9 6
la mise en oeuvre
Je suggère de regarder l'implémentation de cet algorithme en C:
void insertionSortFunction(double array[], int size) {
int i, j, temp;
// i , 1,
for (i = 1; i < size; i++) {
temp = array[i];
for (j = i - 1; j >= 0; j--) {
if (array[j] < temp) {
break;
}
array[j + 1] = array[j];
array[j] = temp;
}
}
}
Une analyse
Je propose d'analyser cet algorithme.
La façon la plus simple de démarrer l'analyse est d'obtenir les asymptotiques de la mémoire. Indépendamment de la longueur et de la structure du tableau proposé pour le tri, la mémoire n'est allouée que pour deux compteurs de boucle et une variable auxiliaire utilisée pour échanger deux valeurs de variable. Ainsi, il est toujours vrai:
...
Au fil du temps, tout est un peu plus intéressant. 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é. Mais le nombre d'itérations de la boucle interne dépend de l'ordre (ou non) des éléments du tableau triés. Plusieurs cas doivent être examinés pour analyse.
Le nombre minimum d'itérations est atteint si le tableau à trier est déjà trié. En effet, pour chaque itération de la boucle for externe, exactement une itération de la boucle interne se produit. C'est ce qu'on appelle le meilleur des cas .
Ainsi, le tri se fait en temps linéaire.
Dans le pire des cas, le nombre d'itérations est supposé être le plus grand, c'est-à-dire que la pause ne se déclenche jamais. Lors de la première itération de la boucle externe, une itération de la boucle interne est effectuée. Lors de la deuxième itération de la boucle externe, 2 itérations de la boucle interne sont effectuées. En poursuivant le raisonnement, nous pouvons arriver à la conclusion qu'à la dernière (n - 1) - ème) itération de la boucle externe (n - 1) itération de la boucle interne sera exécutée. On a:
Pour effectuer les calculs, nous avons utilisé les propriétés de la notation O et la formule de la somme d'une progression arithmétique.
Dans le cas moyen, on suppose que le nombre d'itérations de la boucle interne pour une itération particulière de la boucle externe est égal à sa valeur moyenne, c'est-à-dire l'espérance mathématique. Supposons que tous les nombres autorisés du déclenchement de la boucle interne sont également probables. Dans ce cas, le nombre moyen d'itérations de la boucle interne est de
. I est supposé être le numéro d'itération de la boucle externe. Maintenant, pour calculer les asymptotiques, vous devez calculer 
. Autrement dit, nous comptons simplement combien de fois le corps de la boucle interne est exécuté. Ainsi, nous obtenons 
.
Pour résumer, l'asymptotique mémoire de l'algorithme est
au mieux à temps
et en moyenne et dans le pire des cas
Par conséquent, ce tri appartient à la classe des sortes quadratiques .
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 est appelé 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.
Résultat
Nous avons examiné un autre tri quadratique: le tri par insertion, examiné sa mise en œuvre robuste. Le tri est principalement éducatif, bien qu'en pratique, il puisse être appliqué au mieux en raison de bonnes asymptotiques: si vous devez ajouter de nouvelles données à une quantité suffisamment grande de données ordonnées pour que toutes les données soient à nouveau ordonnées, la boucle for interne peut être utile. Ainsi, il peut être pris en charge pour
ordre du volume de données.
En savoir plus sur le cours.