Algorithme de tri Javascript comptant les compétences de tri example_javascript

Le tri par comptage est un algorithme de tri stable. Le tri par comptage utilise un tableau supplémentaire Count_arr, où le i-ème élément est le nombre d'éléments dont la valeur est égale à i dans le tableau Arr à trier. Organisez ensuite les éléments dans Arr à la position correcte en fonction du tableau Count_arr.
est divisé en quatre étapes :
1. Trouver les éléments les plus grands et les plus petits du tableau à trier
2. Compter le nombre d'occurrences de chaque élément de valeur i dans le tableau et le stocker dans le array Count_arr Item i
3. Accumulez tous les comptes (en commençant par le premier élément de Count_arr, ajoutez chaque élément à l'élément précédent)
4 Parcourez le tableau d'origine à l'envers : ajoutez chaque élément i Placez-le dans le Count_arr. (i) élément du nouveau tableau, et soustrayez Count_arr(i) de 1 pour chaque élément

Exemple :

Copier le code Le code est le suivant :

/**
* Le tri par comptage est un algorithme de tri non basé sur des comparaisons,
* Cet algorithme a été proposé par Harold H. Seward en 1954.
* Son avantage est que lors du tri d'entiers dans une certaine plage,
* Sa complexité est Ο(n k) (où k est la plage d'entiers),
* Plus rapide que n'importe quel algorithme de tri par comparaison .
*
*/

function countSort(arr, min, max) {
var i , z = 0, count = [];

pour (i = min; i <= max; i ) {
count[i] = 0;
}

pour (i=0; i < arr.length; i ) {
count[arr[i]] ;
}

pour (i = min; i <= max; i ) {
while (count[i]-- > 0) {
arr[z ] = i;
}
}
return arr;
}

// test

var i, arr = [];

for (i = 0; i < 100; i ) {
arr.push(Math.floor (Math .random() * (141)));
}

countSort(arr, 0, 140);