Le nombre de sortes plus ou moins différentes les unes des autres est garanti à plus d'une centaine. Parmi eux, il existe des sous-groupes d'algorithmes qui diffèrent au minimum les uns des autres, coïncidant avec une idée principale générale. En fait, au fil des années, différentes personnes reviennent avec les mêmes tris, différant par des détails peu fondamentaux.
Une telle idée algorithmique se retrouve plus souvent que d'autres.
Chaque élément est entré
approximativement à cet endroit du tableau où il doit être situé. Il s'avère qu'un tableau
presque ordonné . À quel tri par insertions est appliqué (il est le plus efficace pour le traitement de tableaux presque ordonnés) ou les zones non ordonnées locales sont traitées récursivement par le même algorithme.
Cet article a été écrit avec le soutien d'EDISON, qui développe une large gamme de solutions pour une variété de tâches: des programmes pour essayer en ligne les vêtements des magasins multimarques au système de transmission LED entre les fleuves et les navires .
Nous aimons la théorie des algorithmes! ;-)
Pour évaluer approximativement où vous voulez placer l'élément, vous devez savoir à quel point il diffère de l'élément moyen du tableau. Pour ce faire, vous devez connaître les valeurs des éléments minimum et maximum, ainsi que la taille du tableau.
Le tableau trié est censé avoir des données vraiment aléatoires. Tous les inventeurs de cette méthode arrivent à la même formule:
k est la place approximative dans le tableau où l'élément
A (
i ) doit être
min ,
max - valeurs des éléments minimum et maximum dans le tableau
ATaille - le nombre d'éléments dans le tableau
AVoici une telle idée générale. Voyons dans quelles variations cet algorithme est né encore et encore.
Tri du roi Salomon :: Tri Salomon
Cette méthode (et son beau nom) a été
proposée par l' utilisateur du
V2008n il y a environ 5 ans. Tout a son temps, «le temps de disperser les pierres et le temps de collecter les pierres» (les mots du roi Salomon du livre de l'Ecclésiaste) - et dans l'algorithme, c'est exactement ce qui se passe. Tout d'abord, à l'aide de la formule, nous dispersons les éléments aux endroits souhaités dans le tableau. Étant donné que la formule ne donne pas une place exacte, mais approximative, plusieurs éléments proches les uns des autres en valeur revendiquent à la fois certaines positions. Ces groupes d'éléments locaux sont triés par insertions puis assemblés dans l'ordre final.
Tri par interpolation
"Il n'y a rien de nouveau sous le soleil", pour reprendre le même auteur. Wikipedia décrit le tri par interpolation, rappelant étrangement le tri de Salomon. Chaque «tas de pierres» est un petit réseau dynamique supplémentaire, où se trouvent des éléments d'importance similaire. La principale différence est qu'après la «diffusion de pierres», ces groupes locaux d'éléments non triés ne sont pas triés par insertions, mais par tri par interpolation (récursivement ou en boucle).
Un tableau ordonné est un ensemble de données discret qui peut être considéré comme un ensemble fini de valeurs connues d'une certaine fonction inconnue. En fait, une distribution approximative du point de vue des mathématiques de calcul - c'est l'interpolation.
Tri d'interpolation JavaScript - BouclageArray.prototype.interpolationSort = function() { var divideSize = new Array(); var end = this.length; divideSize[0] = end; while(divideSize.length > 0) {divide(this);} function divide(A) { var size = divideSize.pop(); var start = end - size; var min = A[start]; var max = A[start]; var temp = 0; for(var i = start + 1; i < end; i++) { if(A[i] < min) { min = A[i]; } else { if(A[i] > max) {max = A[i];} } } if(min == max) { end = end - size; } else { var p = 0; var bucket = new Array(size); for(var i = 0; i < size; i++) {bucket[i] = new Array();} for(var i = start; i < end; i++) { p = Math.floor(((A[i] - min) / (max - min)) * (size - 1)); bucket[p].push(A[i]); } for(var i = 0; i < size; i++) { if(bucket[i].length > 0) { for(var j = 0; j < bucket[i].length; j++) {A[start++] = bucket[i][j];} divideSize.push(bucket[i].length); } } } } };
Tri par interpolation JavaScript - version récursive Array.prototype.bucketSort = function() { var start = 0; var size = this.length; var min = this[0]; var max = this[0]; for(var i = 1; i < size; i++) { if (this[i] < min) { min = this[i]; } else { if(this[i] > max) {max = this[i];} } } if(min != max) { var bucket = new Array(size); for(var i = 0; i < size; i++) {bucket[i] = new Array();} var interpolation = 0; for(var i = 0; i < size; i++){ interpolation = Math.floor(((this[i] - min) / (max - min)) * (size - 1)); bucket[interpolation].push(this[i]); } for(var i = 0; i < size; i++) { if(bucket[i].length > 1) {bucket[i].bucketSort();}
Tri d'histogramme :: Tri d'histogramme
Il s'agit d'une optimisation du tri par interpolation, qui compte le nombre d'éléments appartenant à des groupes locaux non triés. Ce nombre vous permet d'insérer des éléments non triés directement dans le tableau résultant (au lieu de les regrouper dans de petits tableaux séparés).
Tri des barres JavaScript Array.prototype.histogramSort = function() { var end = this.length; var sortedArray = new Array(end); var interpolation = new Array(end); var hitCount = new Array(end); var divideSize = new Array(); divideSize[0] = end; while(divideSize.length > 0) {distribute(this);} function distribute(A) { var size = divideSize.pop(); var start = end - size; var min = A[start]; var max = A[start]; for(var i = start + 1; i < end; i++) { if (A[i] < min) { min = A[i]; } else { if (A[i] > max) {max = A[i];} } } if (min == max) { end = end - size; } else { for(var i = start; i < end; i++){hitCount[i] = 0;} for(var i = start; i < end; i++) { interpolation[i] = start + Math.floor(((A[i] - min) / (max - min)) * (size - 1)); hitCount[interpolation[i]]++; } for(var i = start; i < end; i++) { if(hitCount[i] > 0){divideSize.push(hitCount[i]);} } hitCount[end - 1] = end - hitCount[end - 1]; for(var i = end - 1; i > start; i--) { hitCount[i - 1] = hitCount[i] - hitCount[i - 1]; } for(var i = start; i < end; i++) { sortedArray[hitCount[interpolation[i]]] = A[i]; hitCount[interpolation[i]]++; } for(var i = start; i < end; i++) {A[i] = sortedArray[i];} } } };
Tri des balises d'interpolation
Afin d'optimiser davantage la surcharge, il est proposé ici de ne pas se souvenir du nombre d'éléments similaires dans les groupes non triés, mais simplement de marquer le début de ces groupes avec des drapeaux True / False. Vrai signifie que le sous-groupe est déjà trié et Faux signifie qu'il ne l'est pas encore.
Tri par interpolation avec balise JavaScript Array.prototype.InterpolaionTagSort = function() { var end = this.length; if(end > 1) { var start = 0 ; var Tag = new Array(end);
Tri des balises d'interpolation (sur place)
Si les valeurs des éléments du tableau ne sont pas répétées et uniformément réparties (grosso modo - si les données sous forme triée sont quelque chose comme une progression arithmétique), alors vous pouvez trier en une seule passe, en les triant correctement, sans déplacer les éléments vers des tableaux intermédiaires.
Trier par interpolation avec des étiquettes (en place) en JavaScript Array.prototype.InPlaceTagSort = function() { var n = this.length; var Tag = new Array(n); for(i = 0; i < n; i++) {Tag[i] = false;} var min = this[0]; var max = this[0]; for(i = 1; i < n; i++) { if(this[i] < min) { min = this[i]; } else { if(this[i] > max) {max = this[i];} } } var p = 0; var temp = 0; for(i = 0; i < n; i++) { while(Tag[i] == false) { p = Math.floor(((this[i] - min) / (max - min)) * (n - 1)); temp = this[i]; this[i] = this[p]; this[p] = temp; Tag[p] = true; } } };
Tri Flash :: Flashsort
Il était une fois, j'ai
écrit sur le tri, inventé par le professeur de biophysique Neubert en 1998.
Le professeur a suggéré de répartir les éléments dans plusieurs classes distinctes (l'appartenance à une classe est déterminée par la taille de l'élément). Dans cet esprit, la formule ressemble à ceci:
Au lieu de Size (taille du tableau), la formule indique
m - le nombre de classes selon lesquelles nous distribuons les éléments du tableau. La formule ne calcule pas la clé dans le tableau où l'élément doit être jeté, mais le numéro de classe auquel l'élément appartient.
Ce tri n'est pas mauvais en ce qu'il est plus économique sur la mémoire supplémentaire. La redistribution des éléments a lieu sur place. Seule la localisation des classes est stockée séparément (enfin, si vous regardez sous un angle différent, le nombre d'éléments appartenant à une classe particulière est stocké séparément).
Eh bien, le reste est la même chanson.
Tri Flash en Java class FlashSort { static int n; static int m; static int[] a; static int[] l; public static void flashSort(int size) { n = size; generateRandomArray(); long start = System.currentTimeMillis(); partialFlashSort(); long mid = System.currentTimeMillis(); insertionSort(); long end = System.currentTimeMillis();
Tri approximatif :: Tri Proxmap
Ce tri est le plus ancien de ceux mentionnés ici; il a été introduit en 1980 par le professeur Thomas Standish de l'Université de Californie. En apparence, cela semble être sensiblement différent, mais si vous regardez de près, tout est pareil.
L'algorithme fonctionne avec un concept tel qu'un
hit - un certain nombre dont la valeur est proche d'un élément du tableau.
Pour déterminer si un élément de tableau est un hit, une
fonction d'approximation est appliquée à l'élément.
Le professeur Standish a trié des tableaux de nombres réels. La fonction d'approximation consistait à arrondir les nombres réels à un entier.
C'est, par exemple, si le tableau contient des éléments 2.8, 2, 2.1, 2.6, etc. alors un coup sûr pour ces numéros sera égal.
Procédure générale:
- Nous appliquons une fonction d'approximation à chaque élément, déterminant quel hit correspond à l'élément suivant.
- Ainsi, pour chaque hit, on peut calculer le nombre d'éléments correspondant à ce hit.
- Connaissant le nombre d'éléments pour tous les hits, nous déterminons la localisation des hits (bordures à gauche) dans le tableau.
- Connaissant la localisation des hits, nous déterminons la localisation de chaque élément.
- Après avoir déterminé la localisation de l'élément, nous essayons de l'insérer à sa place dans le tableau. Si la place est déjà prise, alors on déplace les voisins vers la droite (si l'élément est plus petit qu'eux) pour faire de la place à l'élément. Ou à droite nous insérons l'élément lui-même (s'il est plus que des voisins).
En tant que fonction d'approximation, vous pouvez affecter n'importe laquelle en fonction de la nature générale des données du tableau. Dans les implémentations modernes de ce tri, les hits sont généralement déterminés non pas en mordant la partie fractionnaire, mais en utilisant notre formule préférée.
Tri par approximation JavaScript Array.prototype.ProxmapSort = function() { var start = 0; var end = this.length; var A2 = new Array(end); var MapKey = new Array(end); var hitCount = new Array(end); for(var i = start; i < end; i++) {hitCount[i] = 0;} var min = this[start]; var max = this[start]; for (var i = start+1; i < end; i++){ if (this[i] < min) { min = this[i]; } else { if(this[i] > max) {max = this[i];} } }
Tri par insertion de tri par hachage :: Tri par hachage
Eh bien, nous terminerons notre examen avec l'algorithme
que l' évaluateur
bobbyKdas a suggéré il y a 6 ans. Il s'agit d'un algorithme hybride dans lequel, en plus de la distribution et des insertions, la fusion est également ajoutée.
- Le tableau est récursivement divisé en deux, jusqu'à ce qu'à un certain stade, les tailles des demi-sous-réseaux atteignent la taille minimale (l'auteur ne compte pas plus de 500 éléments).
- Au niveau de récursivité le plus bas, un algorithme familier est appliqué à chaque demi-sous-tableau - en utilisant la même formule, une distribution approximative se produit à l'intérieur du sous-tableau, avec un tri par insertions des sections locales non triées.
- Après l'arrangement des deux moitiés des sous-réseaux, ils fusionnent.
- Le point 3 (fusion de demi-sous-matrices triées) est répété lors de la remontée le long des niveaux de récursivité jusqu'au sommet, lorsque le tableau d'origine est combiné à partir de deux moitiés.
Trier par insertion de hachage en Java import java.util.Arrays; import java.util.Date; import java.util.Random; public class HashSort {
La formule elle-même est appelée une fonction de hachage, et le tableau auxiliaire pour la distribution approximative est appelé une table de hachage.
Les références
Interpolation et histogramme ,
Flash ,
Proxmap
Salomon ,
Table de hachage ,
FlashArticles de série:
Le tri par approximation est apparu dans l'application AlgoLab Excel (dans ce cas, dans le tableau initial non trié, la partie fractionnaire aléatoire est ajoutée aux entiers). Salomon et Flash existent depuis longtemps, mais n'ont pas encore implémenté d'interpolation, de hachage et d'histogramme.