current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 12 down vote favorite
3

I've been playing around and reading up on some sorting algorithms, and I've decided to try writing my own. It turned out to be quite fast (compared to the others shown in the image below).

I'm very curious to know a little bit about it:

  • Does my algorithm already have a name?
  • What are the downsides to it (other than it being really stupid to sort { 900000, 1 } with it)?
  • Why is it not a good solution in general?
  • Any suggestions for optimisation?

static int[] MySort(int[] input)
{
    int minValue = input.Min() - 1;
    int[] tempArr = new int[input.Max() - minValue];
    //{1,3,3,5}   becomes:
    //{1,0,2,0,1} one 1's, two 3's, one 5's.
    for (int i = 0; i < input.Length; i++)
        tempArr[input[i] - minValue - 1] += 1;
    //AddNumbers to old array. and add minValue.

    int g = 0;
    for (int j = 0; j < tempArr.Length; j++)
    {
        if (tempArr[j] != 0)
        {
            for (int i = 0; i < tempArr[j]; i++)
            {
                input[g] = j + minValue + 1;
                g++;
            }
        }
    }
    return input;
}

Performance screenshot:

enter image description here

share|improve this question
2  
looks pretty good to me, I haven't tried to do a sort in a very long time. I was curious about one thing, why use a while instead of a for loop? –  Lyle's Mug Sep 13 '13 at 15:19
1  
hah, good question... It seemed like the right thing to do at the time^^, i'll change it –  BjarkeCK Sep 13 '13 at 15:37
    
I have heard that some (or most) programmers frown on while loops unless there is a very good reason to use them, mostly because of infinite loops. with while loops it is easy to fall into an infinite loop –  Lyle's Mug Sep 13 '13 at 15:44
1  
Yeah, dont know why i did while... And also, it improved the performance by 5ms in the example above^^ –  BjarkeCK Sep 13 '13 at 15:46
    
Post rolled back as it invalidated @svick's answer. –  Jamal♦ Sep 13 '13 at 16:56

2 Answers 2

up vote 14 down vote accepted

Does my algorithm already have a name?

It's called counting sort.

What are the downsides to it? (Other than it is really stupid to sort { 900000, 1 } with it.)

That's exactly the major disadvantage of the algorithm: it doesn't work well if the range of values is large.

Why is it not a good solution in general?

Because it can sort only integers. You can't use it to sort floating point numbers, strings or any other type that doesn't behave as an integer.

Any suggestions for optimization?

The condition if (tempArr[j] != 0) is completely useless. If you leave it out, the code will work exactly the same.

share|improve this answer
up vote 2 down vote

I know this is a fairly old question, but I'd like to point something out.

While i and j are commonly used as "counter" variables, they only serve to obfuscate the code in this case. By time we make it to g, it's very difficult indeed to tell which variable stands for what. These should all have meaningful names for Mr. Maintainer's sake.

This is a little more verbose, but (I think) a little easier to understand. Particularly considering that it's easy to see now that the i in the initial loop, is not the same i as the one nested in the second loop.

static int[] MySort(int[] input)
{
    int minValue = input.Min() - 1;
    int[] tempArr = new int[input.Max() - minValue];
    //{1,3,3,5}   becomes:
    //{1,0,2,0,1} one 1's, two 3's, one 5's.
    for (int inputCounter = 0; inputCounter < input.Length; inputCounter++)
        tempArr[input[inputCounter] - minValue - 1] += 1;
    //AddNumbers to old array. and add minValue.

    int itemCounter = 0;
    for (int tempCounter = 0; tempCounter < tempArr.Length; tempCounter++)
    {
        if (tempArr[tempCounter] != 0)
        {
            for (int i = 0; i < tempArr[tempCounter]; i++)
            {
                input[itemCounter] = tempCounter + minValue + 1;
                itemCounter++;
            }
        }
    }
    return input;
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.