Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I come from a background of making MVC websites and HTML5 applications, and have recently decided to dive into the sort of stuff i wasn't taught at university, namely the things most people would learn on a computer science course.

I've been reading a book on algorithms, and the first one it mentions was the Insertion Sort. I didn't really understand it the first time, but I understood the goal, so I had a crack at coming up with my own solution before reading more into the proper solution to see how close I got.

I got pretty close, and here is my function in C#:

    int[] SortNumbersTomsVersion(int[] numbersIn)
    {
        int[] output = new int[numbersIn.Count()];

        for (var i = 0; i < numbersIn.Count(); i++) 
        {
            int cardsLowerThan = 0;

            for (var n = 0; n < numbersIn.Count(); n++) 
            {
                if (numbersIn[n] < numbersIn[i]) 
                {
                    cardsLowerThan++;
                }
            }
            output[cardsLowerThan] = numbersIn[i];
        }
        return output;
    }

The concept of it is that, i start off with a group of numbers. Then, for each number, I compare it to all of the other numbers in the array, to see how many others are lower in value. It then takes the resulting count, and places the current number into an output array at that index. The algorithm goes through all the numbers until they are all at the same location.

My question is, what makes the original better than my solution?

for reference, here is the accepted algorithm outside of a function:

    int temp, k;
    for (int i = 1; i < array_size; i++) 
    {
        temp = array[i];
        k = i - 1;
        while (k >= 0 && array[k] > temp) 
        {
            array[k + 1] = array[k];
            k--;
        }
        array[k + 1] = temp;
    }
share|improve this question
2  
Well, it seems that the "accepted version" sorts in-place, while yours makes a copy and thus requires 2x more memory. But seriously, why do you suspect the original is better? Performance? Readability? –  Daniel B Aug 23 '12 at 14:02
    
Because I'm pretty certain i'm not the first person to come up with this solution, as I have very little CS background, so I imagine if mine was better, it would be the standard. –  Tom Halley Aug 23 '12 at 14:05
1  
Hey Tom, why not?, you may discover a better solution for a problem than the rest of the world, just keep trying. –  Emmad Kareem Aug 23 '12 at 15:00
add comment

1 Answer

up vote 5 down vote accepted

Comparing performance of 2 algorithms, assuming both work correctly, involves several factors such as space, speed, etc. Without detailed analysis, your code has nested for loops each bound by (n) iterations:

for (var i = 0; i < numbersIn.Count(); i++) 
     {   
            ...

            for (var n = 0; n < numbersIn.Count(); n++) ...}}

this calls for O(n*n) even at the best case (when elements are already sorted). The insertion sort algorithm is supposed to be O(n) in the best case see: Wiki-InsertionSort.

share|improve this answer
add comment

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.