Optimize a list<T>.Sort(Comparer)

Question

Hi,

I have a list which stores a lost of integers. I don't like the default List.Sort() works, as I want the list to be ordered by size of the actual int. So far I have this:

Oh, and the ints are stored in strings, e.g "1234". It is something I can not change.

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;
            }
        }
    }
}

But to my knowledge, this is bubble-sort, correct? What should I implement instead? Quicksort? also, I might need help writing it.

Oh and my list contains short of 2 thousand elements which stores numbers in strings

Also, I call my IComparer like this:

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

Answer 1

You should be aware that the comparer and the sort algorithm do not determine each other. So this comparer can be used with bubble-sort as well as with quicksort, heapsort or any other sort algorithm. The built-in sort algorithm of List.Sort is quicksort, according to MSDN.

Answer 2

So you have a list of strings representing ints as input and you want a sorted list of ints as output?

You seem to be doing a lot of work here to get the results you want - you could leverage some Linq to get your results like this:

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);
     }
    }
}

And I wouldn't be concerned about optimising your sort algorithm manually with 2 thousand items - that's not really so many items to sort unless that's 'all' your application is doing.

Answer 3

Assuming you want to sort by the value of the integer stored as a string, you can simply do something like this:

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

Answer 4

No, the algorithm used for sorting a list is QuickSort, so you can't easily improve on that.

List<T>.Sort method

This method uses Array.Sort, which uses the QuickSort algorithm.

I completed the comparer:

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:
I added a faster integer parser. As the comparer doesn't handle negative values, the parser doesn't either, which allowed for some further optimising.

Answer 5

Here is a quick example as long as you are using a .net 3.5 project (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

I think you should first convert the strings to a temporary list of int as the other code here (so far) converts the strings over and over again, for each comparison. (You could also use nullable ints if keeping the nulls around is important). After that, you sort the list and if necessary convert back to strings.