4

Yesterday at work I set out to figure out how to sort numbers without using the library method Array.Sort. I worked on and off when time permitted and finally was able to come up with a basic working algorithm at the end of today. It might be rather stupid and the slowest way, but I am content that I have a working code.

But there is something wrong or missing in the logic, that is causing the output to hang before printing the line: Numbers Sorted. (12/17/2011 2:11:42 AM)

This delay is directly proportionate to the number of elements in the array. To be specific, the output just hangs at the position where I put the tilde in the results section below. The content after tilde is getting printed after that noticeable delay.

Here is the code that does the sort:

while(pass != unsortedNumLen)
{
    for(int i=0,j=1; i < unsortedNumLen-1 && j < unsortedNumLen; i++,j++)
    {
        if (unsorted[i] > unsorted[j])
        {
            pass = 0;
            swaps++;
            Console.Write("Swapping {0} and {1}:\t", unsorted[i], unsorted[j]);
            tmp = unsorted[i];
            unsorted[i] = unsorted[j];
            unsorted[j] = tmp;
            printArray(unsorted);
        }

        else pass++;
    }
}

The results:

Numbers unsorted. (12/17/2011 2:11:19 AM)

4 3 2 1
Swapping 4 and 3:       3 4 2 1
Swapping 4 and 2:       3 2 4 1
Swapping 4 and 1:       3 2 1 4
Swapping 3 and 2:       2 3 1 4
Swapping 3 and 1:       2 1 3 4
Swapping 2 and 1:       1 2 3 4
~
Numbers sorted. (12/17/2011 2:11:42 AM)

1 2 3 4
Number of swaps: 6

Can you help identify the issue with my attempt?

Link to full code
This is not homework, just me working out.

Improve this question
9
  • Just curious, why aren't you just using Array.Sort()? Or LINQ OrderBy()? Commented Dec 16, 2011 at 21:21
  • 4
    You have "discovered" bubble sort. There are much better ways: en.wikipedia.org/wiki/Sorting_algorithm Commented Dec 16, 2011 at 21:23
  • 1
    @JamesMichaelHare: I am aware of both Array.Sort() and LINQ OrderBy(). I am trying this out to exercise my mind. Nothing serious. I would not use this in any serious project. Commented Dec 16, 2011 at 21:25
  • @dlev: I see. I vaguely remember an algorithm from my college days and tried to materialize it. Thanks for letting me know which sort it is in particular Commented Dec 16, 2011 at 21:26
  • 1
    I just meant that if you have a program, and you are printing intermediate state using Console.Write(), the Console.Out is buffered. Thus when you call Write() it puts data into the buffer. Once the buffer is full, or a call to Console.Read(), etc is called, it will flush that buffer to the screen. Thus if you have something like: Operations(); Console.Write("1"); Operations(); Console.Write("2"); Operations(); Console.Write("3"); and Operations() takes a long time, it's possible you'll see a long "hang" and then 1, 2, 3 pop up at the end. So just be wary of timing of output. Commented Dec 16, 2011 at 21:52

4 Answers 4

Reset to default
6

Change the condition in your while to this:

while (pass < unsortedNumLen)

Logically pass never equals unsortedNumLen so your while won't terminate.

pass does eventually equal unsortedNumLen when it goes over the max value of an int and loops around to it.

In order to see what's happening yourself while it's in the hung state, just hit the pause button in Visual Studio and hover your mouse over pass to see that it contains a huge value.

You could also set a breakpoint on the while line and add a watch for pass. That would show you that the first time the list is sorted, pass equals 5.

Improve this answer
Sign up to request clarification or add additional context in comments.

12 Comments

EDIT: My bad, I misunderstood your answer (and maybe the downvoter did too?) In any case, I think your answer could be made clearer (since obviously pass does take on the correct value at some point) but it is, in general, correct. Consider changing "never" to "will take a long to be", since the whole point is that pass will continually wrap around until you get lucky and it ends up at unsortedNumLen.
@loudsight No it most certainly is not set to zero every time the for loop is executed. If the numbers are already in order, the if block is never executed, only the else.
@Dennis I executed it in LINQPad, upvoted you, and added my own answer as a "teach a man to fish" alternative.
pass exceeds unsortedNumLen well before it equals it. :)
@KishorNanda that makes sense. Glad you're here and learning the why behind what you're doing!
|
4

It sounds like you want a hint to help you work through it and learn, so I am not posting a complete solution.

Change your else block to the below and see if it puts you on the right track.

else {

    Console.WriteLine("Nothing to do for {0} and {1}", unsorted[i], unsorted[j]);
    pass++;
}
Improve this answer

9 Comments

I added the print statement in the else clause like you have said. It printed an infinite number of prints, which is what is causing the delay. Thanks
@Kishor, it is not infinite if it eventually exits, and your original posted output proves that it does. The extra writes will slow things down even further, but now you should be seeing that you're continuing to run through the loop even though there is no more work to be done. See Andrei's answer for a detailed explanation of why it takes so long for pass to equal unsortedNumLength.
Again I'm trying to not give away the answer because I get a feeling you want to practice a thought process, which is a fantastic and rare thing these days.
@Kishor Glad to help. Stick with it and hold on to your dedication to thinking / learning!
@DavidRuttka "it is not infinite if it eventually exits" well yes but it doesn't always exit. It depends on the number of elements. For example if the number of elements is 5 it won't ever exit. This is because while(pass != unsortedNumLen) isn't evaluated after every increment of pass. 7 won't either. It may be that odd values the number of elements do this. This also explains why different numbers of elements can take longer. For example when the number of elements is 6 it takes 5 iterations of overflows to get pass == unsortedNumLen
|
2

Here is the fix:

while(pass < unsortedNumLen)

And here is why the delay occurred.

After the end of the for loop in which the array was eventually sorted, pass contains at most unsortedNumLen - 2 (if the last change was between first and second members). But it does not equal the unsorted array length, so another iteration of while and inner for starts. Since the array is sorted unsorted[i] > unsorted[j] is always false, so pass always gets incremented - exactly the number of times j got incremented, and that is the unsortedNumLen - 1. Which is not equal to unsortedNumLen, and so another iteration of while begins. Nothing essentially changed, and after this iteration pass contains 2 * (unsortedNumLen - 1), which is still not equal to unsortedNumLen. And so on.

When pass reaches value int.MaxValue, it the overflow happens, and next value the variable pass will get is int.MinValue. And the process goes on, until pass finally gets the value unsortedNumLen at the moment the while condition is checked. If you are particularly unlucky, this might never happen at all.

P.S. You might want to check out this link.

Improve this answer

4 Comments

pass actually equals unsortedNumLen + 1 when the list is correctly sorted.
Actually no, it equals 0. This version of bubble sort "bubbles down", sort to say, i.e. most likely the latest change will take place between first and second elements of the array. At this moment pass equals 0. However at the end of the for loop in which the array was sorted, pass equals unsortedNumLen - 2. But I see the point - will update the answer, thanks.
The name comes from the values "bubbling" up, rather than the swap points sinking down after each high value is in place. It has also been called "sinking" sort for that reason (and people thought it should have a negative sounding name rather than a happy one), but that name is disputed since it's also used for insertion sorts.
@Andrei Right. I was looking at it from the perspective of the while condition. It does increment by unsortedNumLen - 1 in successive iterations.
1

This is just a characteristic of the algorithm you're using to sort. Once it's completed sorting the elements it has no way of knowing the sort is complete, so it does one final pass checking every element again. You can fix this by adding --unsortedNumLen; at the end of your for loop as follows:

for(int i=0,j=1; i < unsortedNumLen-1 && j < unsortedNumLen; i++,j++)
{
/// existing sorting code
}
--unsortedNumLen;

Reason? Because you algorithm is bubbling the biggest value to the end of the array, there is no need to check this element again since it's already been determined to be larger the all other elements.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.