Comment trier un tableau de chaînes?

Question

J'ai une liste de mots d'entrée séparés par des virgules. Je veux trier ces mots par ordre alphabétique et longueur. Comment puis-je faire cela sans utiliser les fonctions de tri intégrées?

Answer 1

Bonne question !! Le tri est probablement le concept le plus important à apprendre en tant qu'informaticien émergent.

Il existe actuellement beaucoup d'algorithmes différents pour trier une liste.

Lorsque vous cassez tous ces algorithmes, l'opération la plus fondamentale est la comparaison de deux éléments dans la liste, en définissant leur "ordre naturel".

Par exemple, afin de trier une liste d'entiers, je besoin d'une fonction qui me dit, étant donné les deux entiers X et Y si X est inférieur, égal ou supérieur à Y.

Pour vos chaînes, vous aurez besoin de la même chose: une fonction qui vous indique laquelle des chaînes a la valeur "moindre" ou "plus grande", ou si elles sont égales.

Traditionnellement, ces fonctions « de comparaison » ressemblent à ceci:

int CompareStrings(String a, String b) { 
    if (a < b) 
     return -1; 
    else if (a > b) 
     return 1; 
    else 
     return 0; 
} 

J'ai laissé quelques-uns des détails (comme, comment voulez-vous calculer si un est inférieur ou supérieur à b indice? : itérer à travers les caractères), mais c'est le squelette de base de toute fonction de comparaison. Il renvoie une valeur inférieure à zéro si le premier élément est plus petit et une valeur supérieure à zéro si le premier élément est supérieur, renvoyant zéro si les éléments ont la même valeur.

Mais qu'est-ce que cela a à voir avec le tri?

Un routage de tri appellera cette fonction pour les paires d'éléments dans votre liste, en utilisant le résultat de la fonction pour savoir comment réorganiser les éléments dans une liste triée. La fonction de comparaison définit «l'ordre naturel» et «l'algorithme de tri» définit la logique d'appel et de réponse aux résultats de la fonction de comparaison.

Chaque algorithme est comme une stratégie à grande image pour garantir que toute entrée sera triée correctement. Voici quelques-unes des algorithmes que vous aurez probablement envie de savoir:

Trier Bubble:

Itérer dans la liste, en appelant la fonction de comparaison pour toutes les paires adjacentes d'éléments. Chaque fois que vous obtenez un résultat supérieur à zéro (ce qui signifie que le premier élément est plus grand que le second), permutez les deux valeurs. Ensuite, passez à la paire suivante. Lorsque vous arrivez à la fin de la liste, si vous n'avez pas besoin d'échanger des paires, alors félicitations, la liste est triée! Si vous avez dû effectuer des échanges, revenez au début et recommencez. Répétez ce processus jusqu'à ce qu'il n'y ait plus d'échanges. REMARQUE: ce n'est généralement pas un moyen très efficace de trier une liste, car dans le pire des cas, il peut être nécessaire d'analyser toute la liste jusqu'à N fois, pour une liste avec N éléments.

Fusion Trier:

C'est l'un des algorithmes diviser pour régner pour le tri d'une liste des plus populaires. L'idée de base est que, si vous avez deux listes déjà triées, il est facile de les fusionner. Commencez juste au début de chaque liste et supprimez le premier élément de la liste ayant la plus petite valeur de départ. Répétez ce processus jusqu'à ce que vous ayez consommé tous les éléments des deux listes, et vous avez terminé!

1  4  8  10  
    2  5 7  9 
------------ becomes ------------> 
1 2 4 5 7 8 9 10 

Mais que se passe-t-il si vous n'avez pas deux listes triées? Que faire si vous avez une seule liste, et ses éléments sont dans un ordre aléatoire?

C'est la chose intelligente à propos de tri fusion. Vous pouvez casser une liste unique en petits morceaux, dont chacun est soit une liste non triés, une liste triée, ou un seul élément (qui, si vous chose à ce sujet, est en fait une liste triée, avec la longueur = 1). La première étape d'un algorithme de tri par fusion consiste donc à diviser votre liste globale en sous-listes de plus en plus petites. Aux plus petits niveaux (où chaque liste ne comporte qu'un ou deux éléments), ils sont très faciles à trier. Et une fois triés, il est facile de fusionner deux listes triées adjacentes en une liste triée plus grande contenant tous les éléments des deux sous-listes.

REMARQUE: Cet algorithme est beaucoup mieux que la méthode de tri à bulles, décrit ci-dessus, en termes de son efficacité pire cas scénario. Je ne vais pas entrer dans une explication détaillée (ce qui implique un peu de mathématiques assez trivial, mais il faudra un certain temps pour expliquer), mais la raison rapide pour l'efficacité accrue est que cet algorithme se casse le problème en morceaux de taille idéale et se confond alors la les résultats de ces morceaux. L'algorithme de tri à bulles aborde le tout en même temps, donc il n'a pas l'avantage de "diviser pour régner".

---

Ce sont seulement deux algorithmes pour trier une liste, mais il y a beaucoup d'autres techniques intéressantes, chacun avec ses propres avantages et inconvénients: Trier rapide, Radix Trier, Sélection Trier, Heap Trier, Shell Trier, et Seau Trier.

Internet regorge d'informations intéressantes sur le tri. Voici un bon endroit pour commencer:

http://en.wikipedia.org/wiki/Sorting_algorithms

Answer 2

Il y a un domaine entier d'étude construit autour de sorting algorithms. Vous pouvez en choisir un simple et l'implémenter.

Bien que ce ne soit pas le plus performant, cela ne devrait pas prendre trop de temps pour implémenter un bubble sort.

Answer 3

Créez une application de console et collez-la dans le fichier Program.cs en tant que corps de la classe.

public static void Main(string[] args) 
{ 
    string [] strList = "a,b,c,d,e,f,a,a,b".Split(new [] { ',' }, StringSplitOptions.RemoveEmptyEntries); 

    foreach(string s in strList.Sort()) 
     Console.WriteLine(s); 
} 

public static string [] Sort(this string [] strList) 
{ 
    return strList.OrderBy(i => i).ToArray(); 
} 

Notez que je ne l'utilise construit dans la méthode, OrderBy. Comme d'autres réponses le signalent, il existe de nombreux algorithmes de tri différents que vous pouvez implémenter ici et je pense que mon extrait de code fait tout pour vous, sauf l'algorithme de tri réel.

Some C# specific sorting tutorials

Answer 4

Si vous ne souhaitez pas utiliser build-in-fonctions, vous devez créer un par votre auto. Je recommande Bubble sort ou un algorithme similaire. Le tri des bulles n'est pas un algorithme efficace, mais il permet de faire les choses et est facile à comprendre.

Vous trouverez beaucoup de bonnes lectures sur wikipedia.

Answer 5

Je recommanderais de faire un wiki pour quicksort.

Vous ne savez toujours pas pourquoi vous ne voulez pas utiliser le tri intégré?

Answer 6

dommages de tri Bubble le cerveau.

Le tri par insertion est au moins aussi simple à comprendre et à coder, et il est réellement utile dans la pratique (pour de très petits ensembles de données et des données presque triées). Cela fonctionne comme ceci:

Supposons que les n premiers éléments sont déjà dans l'ordre (vous pouvez commencer par n = 1, car évidemment une chose à part est "dans le bon ordre"). Prenez le (n + 1) ième élément dans votre tableau. Appelez cela le "pivot". En commençant par le nième élément et en descendant:
    - s'il est plus grand que le pivot, déplacez-le d'un espace vers la droite (pour créer un "espace" à sa gauche). - sinon, laissez-le en place, placez le "pivot" à droite de celui-ci (c'est-à-dire dans le "trou" si vous avez bougé quelque chose, où il a commencé si vous n'avez rien déplacé) et arrêtez .

Maintenant, les n + 1 premiers éléments du tableau sont dans l'ordre, parce que le pivot est à la droite de tout ce qui est plus petit que lui, et à la gauche de tout ce qui est plus grand que lui. Puisque vous avez commencé avec n éléments dans l'ordre, c'est un progrès. Répétez, en augmentant de 1 à chaque étape, jusqu'à ce que vous ayez traité la liste entière.

Ceci correspond à une façon de placer physiquement une série de dossiers dans un classeur dans l'ordre suivant: mettre un dans; puis en mettre un autre dans sa position correcte en poussant tout ce qui lui appartient après un espace pour faire de la place; répétez jusqu'à la fin. Personne ne trie jamais les objets physiques par type de bulle, donc c'est un mystère pour moi pourquoi c'est considéré comme "simple". Tout ce qui reste maintenant, c'est que vous devez être en mesure de travailler, à deux cordes, si le premier est plus grand que le second. Je ne suis pas sûr de ce que vous entendez par "alphabétique et longueur": l'ordre alphabétique est fait en comparant un caractère à la fois de chaque chaîne. S'il n'y a pas la même chose, c'est votre commande. Si elles sont identiques, regardez la suivante, sauf si vous n'avez plus de caractères dans l'une des chaînes, auquel cas c'est celui qui est "plus petit".

Answer 7

Utilisez NSort

Je couru à travers la bibliothèque il y a NSort quelques années dans le livre Windows Developer Power Tools. La bibliothèque NSort implémente un certain nombre d'algorithmes de tri. Le principal avantage d'utiliser quelque chose comme NSort sur l'écriture de votre propre tri est qu'il est déjà testé et optimisé.

Answer 8

lien d'affichage au code de tri de chaîne rapide en C#:

http://www.codeproject.com/KB/cs/fast_string_sort.aspx

Un autre point: Le comparateur proposé ci-dessus n'est pas recommandé pour les langues non anglais:

int compareStrings (String a, Chaîne b) {
si (a < b) renvoie -1;
sinon si (a> b)
retour 1;
return 0; }

Commander ce lien pour le tri de langue non-anglaise:

http://msdn.microsoft.com/en-us/goglobal/bb688122

Et comme mentionné, l'utilisation nsort pour les tableaux vraiment gigantesques qui ne correspondent pas à la mémoire.