Optimiser une liste <T> .Sort (Comparer)

Question

J'ai une liste qui stocke une perte d'entiers. Je n'aime pas le fonctionnement par défaut de List.Sort(), car je veux que la liste soit ordonnée par la taille de l'int réel. Jusqu'ici j'ai ceci:

Oh, et les ints sont stockés dans des chaînes, par exemple "1234". C'est quelque chose que je ne peux pas changer.

public class IntComparer : IComparer<string> 
{ 
    public int Compare(string x, string y) 
    { 
     if (x == null) 
     { 
      if (y == null) 
      { 
       // If x is null and y is null, they're 
       // equal. 
       return 0; 
      } 
      else 
      { 
       // If x is null and y is not null, y 
       // is greater. 
       return -1; 
      } 
     } 
     else 
     { 
      // If x is not null... 
      // 
      if (y == null) 
      // ...and y is null, x is greater. 
      { 
       return 1; 
      } 
      else 
      { 
       // ...and y is not null, compare the 
       // lengths of the two strings. 
       // 
       int xInt = Convert.ToInt32(x); 
       int yInt = Convert.ToInt32(y); 

       if (x > y) 
       { 
        // If the strings are not of equal length, 
        // the longer string is greater. 
        // 
        return 1; 
       } 
       else if (xInt == yInt) 
       { 
        return 0; 
       } 
       else 
       { 
        // If the strings are of equal length, 
        // sort them with ordinary string comparison. 


     // 
       return -1; 
      } 
     } 
    } 
} 

Mais à ma connaissance, il s'agit d'un tri des bulles, n'est-ce pas? Que devrais-je implémenter à la place? Tri rapide? aussi, je pourrais avoir besoin d'aide pour l'écrire.

Oh, et ma liste contient peu de 2 mille éléments qui stocke les numéros dans les chaînes

Aussi, j'appeler mon IComparer comme ceci:

IntComparer intSort = New IntComparer(); 
List<T>.Sort(intSort); 

Answer 1

En supposant que vous voulez trier la valeur de l'entier stocké sous forme de chaîne, vous pouvez simplement faire quelque chose comme ceci:

numbers.Sort((x,y) => Int32.Parse(x).CompareTo(Int32.Parse(y))); 

Answer 2

Vous devez savoir que le comparateur et l'algorithme de tri ne vous déterminez pas. Donc, ce comparateur peut être utilisé avec le tri des bulles ainsi qu'avec le quicksort, le heapsort ou tout autre algorithme de tri. L'algorithme de tri intégré de List.Sort est quicksort, selon MSDN.

Answer 3

Vous avez donc une liste de chaînes représentant ints en entrée et vous voulez une liste triée d'ints en sortie?

Vous semblez faire beaucoup de travail ici pour obtenir les résultats que vous voulez - vous pouvez tirer parti de certains LINQ pour obtenir vos résultats comme celui-ci:

using System;

using System.Collections.Generic; 
using System.Linq; 

namespace ConsoleApplication6 
{ 
    internal class Program 
    { 
     private static void Main(string[] args) 
     { 
      var unsortedListOfStringsAsInts = new List<string> {"1234", "2345", "7", "9"}; 
      var sortedListOfInts = unsortedListOfStringsAsInts.Select(x => int.Parse(x)).OrderBy(x => x).ToList(); 

      foreach (var i in sortedListOfInts) 
       Console.WriteLine(i); 
     } 
    } 
} 

Et je ne serais pas préoccupé par l'optimisation de votre algorithme de tri manuellement avec 2 mille articles - ce n'est pas vraiment tant d'articles à trier, à moins que fait est «tout votre application.

Answer 4

Non, l'algorithme utilisé pour le tri d'une liste est QuickSort, afin que vous puissiez pas facilement améliorer cela.

List<T>.Sort method

Cette méthode utilise Array.Sort, qui utilise l'algorithme QuickSort.

J'ai terminé le comparateur:

public class IntComparer : IComparer<string> { 

    private static int ParseInt32(string text) { 
     long value = 0; 
     foreach (char c in text) { 
       if (c >= '0' && c <= '9') { 
       value = value * 10 + c - '0'; 
      } else { 
       throw new FormatException(); 
      } 
     } 
     if (value > int.MaxValue) throw new OverflowException(); 
     return (int)value; 
    } 


    public int Compare(string x, string y) { 
     if (x == null) { 
      if (y == null) { 
       // If x is null and y is null, they're 
       // equal. 
       return 0; 
      } else { 
       // If x is null and y is not null, y 
       // is greater. 
       return -1; 
      } 
     } else { 
      // If x is not null... 
      // 
      if (y == null) { 
       // ...and y is null, x is greater. 
       return 1; 
      } else { 
       // ...and y is not null, compare the 
       // lengths of the two strings. 
       // 
       if (x.Length != y.Length) { 
        // If the strings are not of equal length, 
        // the longer string is greater. 
        return x.Length - y.Length; 
       } else { 
        // compare numerically 
        int xInt = ParseInt32(x); 
        int yInt = ParseInt32(y); 
        return xInt - yInt; 
       } 
      } 
     } 
    } 

} 

Edit:
J'ai ajouté un analyseur plus rapide entier. Comme le comparateur ne gère pas les valeurs négatives, l'analyseur ne le fait pas non plus, ce qui a permis d'optimiser davantage.

Answer 5

Voici un exemple rapide tant que vous utilisez un .net 3.5 projet (LINQ)

using System.Linq; 
using System.Collections.Generic; 

List<string> unorderedList = List<string>(); 
list.Add("3"); 
list.Add("5"); 
list.Add("2"); 
list.Add("10"); 
list.Add("-6"); 
list.Add("7"); 

List<string> orderedList = list.OrderBy(x => int.Parse(x)).ToList(); 

Answer 6

Je pense que vous devez d'abord convertir les string s à une liste temporaire de int que l'autre code ici (jusqu'à présent) convertit les chaînes encore et encore, pour chaque comparaison. (Vous pouvez également utiliser des valeurs nulles s'il est important de garder les null autour). Après cela, vous triez la liste et, si nécessaire, vous convertissez en chaînes.