Quel est le meilleur algorithme de tri pour trier un tableau de petits entiers?
Que par question de titre, si le tableau est d'une longueur impaire et les éléments du tableau sont numérotées de 1 à 10.
Exemple,
3 6 8 1 3 7 7 9 4 1
Je pensais de l'aide heapsort? Puisque c'est un tableau, de fusion tri et le tri par insertion nécessite de changer, et de ne pas être si efficace.
source d'informationauteur user236501
Vous devez vous connecter pour publier un commentaire.
Avec cette restriction, comptage de tri sera beaucoup plus efficace que toutes les fins générales de l'algorithme de tri - elle est O(n)
C'est mon comptage, de tri exemple
S'il y a seulement 10 éléments, il n'est pas utile de votre temps à vous inquiéter à ce sujet. Si il y a un million il pourrait commencer à devenir important.
Edit: Un comptage, le tri est probablement optimale compte tenu de la contrainte que les éléments de la gamme de 1 à 10. Un comptage de tri appliqué à ce problème va s'exécuter en O(n) fois. Une sorte de fusion (comme je l'ai recommandé ci-dessous) sera exécuté en rien de mieux que O(nlogn). Parallélisation d'un comptage de tri pourrait être intéressant. Il suffit d'attribuer un subarray avec n/p des éléments de chaque processeur. Chaque processeur a sa propre décompte tableau de taille 9. Cette étape devrait prendre en O(n/p). Puis consolider toutes le comte de tableaux dans un seul tableau, qui devrait prendre de O(p) temps. Je n'ai pas entièrement pensé par le biais de la dernière étape du processus de comptage, de tri où les éléments sont placés dans l'ordre, mais il semble aussi longtemps que les éléments du comte de tableau sont atomiques, vous pouvez assigner n/p sections du tableau original pour les différents processeurs et d'obtenir quelques parallélisation. Il y aurait des conflits sur les différents éléments du comte de tableau, cependant, potentiellement, à la réduction substantielle de la concurrence. Vous pourriez être en mesure d'attribuer les paragraphes du comte de matrice à p processeurs et vous êtes de retour à O(n/p) de l'exécution, si les éléments sont répartis de manière assez homogène, mais vous serait limité à 10 processeurs. Si les éléments ne sont pas répartis uniformément, un ou plusieurs processeurs, pourrait faire une plus grande proportion de l'œuvre. C'est une grande question, pouvez vous faire un comptage de tri en O(n/p) de temps?
Quicksort est une grande place algorithme de tri qui court vite et d'économiser la mémoire. Cependant, étant donné les éléments de la gamme de 1 à 10, si vous êtes de tri un grand nombre d'éléments, vous allez vous retrouver avec de grandes courses du même nombre, soit au départ ou à l'intermédiaire de fois pendant le tri. Dans l'ordre des ensembles ou sous-ensembles peut vraiment ralentir un Quicksort.
Si vous n'avez pas de soins sur la mémoire, un simple Mergesort suffirait. Mergesort est là-haut avec la manière la plus rapide standard algorithmes de tri.
Les Collections par défaut.sort() de la mise en œuvre en Java 7 est un Mergesort algorithme adapté de " TimSort.' La valeur par défaut des Tableaux.sort() de la mise en œuvre en Java 7 est un double pivot Quicksort.
Si vous voulez aller de l'parallèle, un Parallèle Quicksort pouvez obtenir de bons résultats sur de grands tableaux avec de petits nombres de processeurs, mais avec les mêmes restrictions que l'ordre de tri rapide. Le SRFP peut aider à réduire à un plus grand nombre de processeurs.
Vous devriez envisager de regarder cette complexité graphique La Complexité Tableau De Comparaison.
La comparaison de l'algorithme de tri est basé sur de leur Mieux, en Moyenne, le scénario du Pire cas pour le temps et l'espace de la complexité.Basé sur ce tableau, vous pouvez voir Comptage De Tri approche est la meilleure sur le temps et l'espace de la complexité. Autre méthode comparable est Radix de Tri.
Pire [le Temps,l'Espace] la complexité du "Comptage de Tri" :- [O(n+k),O(k)].
Pire [le Temps,l'Espace] la complexité de "Radix Sort" :- [O(nk),O(n+k)].
ceci est un exemple de tri simple (le tri par Insertion)
Comptage tri sera meilleur dans ce scénario.
En supposant que les données sont des nombres entiers, dans une gamme de 0-k. Créer un tableau de taille K pour garder une trace de la façon dont de nombreux éléments apparaissent (3 éléments avec la valeur 0, 4 éléments avec la valeur 1, etc). Compte tenu de ce nombre, vous pouvez indiquer la position d'un élément toutes les 1 doit venir après le 0, de qui il y a 3. Par conséquent, le 1er est de commencer à l'item #4. Ainsi, nous pouvons numériser les éléments et de les insérer dans leur position correcte.
Compter de la création de la matrice est en O(N)
L'insertion des éléments dans leur position correcte est O(N)
J'ai simplifié à l'extrême — il y a une somme de chiffres, et un plus grand à moins de commande qui maintient le tri stable.