Sort arrays of numbers

Question

Yesterday at work, I decided to figure out how to sort numbers without using the library method Array.Sort . I worked and worked when time was allowed, and finally, at the end of today I was able to find the basic algorithm of work. This might be pretty dumb and slower, but I'm glad that I have working code.

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

This delay is directly proportional to the number of elements in the array. To be specific, the output simply hangs in the position where I put the tilde in the results section below. Content after the tilde is printed after this noticeable delay.

Here is the code that does the sorting:

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

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 problem with my attempt?

Link to the full code
This is not homework, I just work.

Answer 1

It looks like you need a hint to help you figure this out and find out, so I am not sending a complete solution.

Change the else block to the following 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++; } 

Answer 2

Change the condition in your while to the following:

 while (pass < unsortedNumLen) 

Logically, pass never equal to unsortedNumLen , so your while will not complete.

pass ultimately equals unsortedNumLen when it goes to the maximum value of int and crosses it.

To see what happens when it is in a hang state, just click the pause button in Visual Studio and hover over pass to see that it contains huge value.

You can also set a breakpoint on the while line and add a clock for pass . This will show you that the first time you sort the list, pass is 5.

Answer 3

Here is the fix:

 while(pass < unsortedNumLen) 

And that is why there was a delay.

After the for loop in which the array was sorted unsortedNumLen - 2 , pass contains no more than unsortedNumLen - 2 (if the last change was between the first and second members). But it is not equal to the length of the unsorted array, so another iteration of while and internal for begins. Since the array is sorted, unsorted[i] > unsorted[j] always false, so pass always gets an increment - it’s exactly the number of times j increased, and this is unsortedNumLen - 1 . This is not equal to unsortedNumLen , and therefore another iteration of while begins. Nothing has changed significantly, and after this iteration pass contains 2 * (unsortedNumLen - 1) , which is still not equal to unsortedNumLen . And so on.

When the pass reaches the value of int.MaxValue , it overflows, and the next value that the pass variable receives is int.MinValue . And the process continues until pass gets unsortedNumLen at the time the while condition is checked. If you're particularly unlucky, this may never happen at all.

PS You can check this link.

Answer 4

This is just a characteristic of the algorithm you use for sorting. Once he has finished sorting the elements, he has no way of knowing that the sorting is complete, so he makes one last pass, checking each element again. You can fix this by adding --unsortedNumLen; at the end of the for loop as follows:

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

Cause? Since the bubble algorithm has the greatest value at the end of the array, there is no need to check this element again, since it is already defined as more than all other elements.