I can't seem to get this sorting alogorithm to work:

#include <iostream>


void sortAssending(int nums[], int size);

int main()
{
    int nums[] = {175,167,160,164,183,187,188,179,176,175,
                  169,175,176,178,165,160,173,165,187,178};
    sortAssending(nums, 20);
    for (int i=0; i<20; i++)
    {
        std::cout << nums[i] << std::endl;
    }
    
    system("PAUSE");
}

void sortAssending(int nums[], int size)
{
     for (int start=0; start<size; start++)
     {
         for (int end=size-1; end>=0; end--)
         {
             if (nums[start] > nums[end])
             {
                 int temp = nums[start];
                 nums[start] = nums[end];
                 nums[end] = temp;
             }
         }
     }
}

It seems to do everything right except the very last number is not in place. Can anyone spot the problem?

The two loops are not correct. Outer-most loop runs from 0 to (start-1). Inner-most loop runs from (outer_loop_counter+1) to start. There are other ways to do it, but I find this algorithm the most logical (easiest to comprehend) because neither loop counts backwards.

void sortAssending(int nums[], int size)
{
     for (int start=0; start< (size-1); start++)
     {
         for (int end=start+1; end < size; end++)
         {
             if (nums[start] > nums[end])
             {
                 int temp = nums[start];
                 nums[start] = nums[end];
                 nums[end] = temp;
             }
         }
     }
}
Comments
thanks
if (nums[start] > nums[end])
             {
                 int temp = nums[start];
                 nums[start] = nums[end];
                 nums[end] = temp;
             }

Since end can iterate down to zero, the comparison can result in swappage in the wrong direction. Here's what happens.

When this algorithm is run, the value 'start' ends up dragging up the least element with it. That is, in the middle of your algorithm, your array might look something like this:

2
3
4
1
7  start
6
8
5
9 end

Then, while 'end' iterates downwards, it puts the smallest element between 'start' and 'end' into the position beneath 'start'. In this case, it swaps 5 with 7, and no more swaps are made.

2
3
4
1
5 start
6  ^
8  |
7 end
9

Then 'end' reaches the position just before 'start'. Since nums[start] > nums[end], the two are swapped.

2
3
4
5 end (after swapping)
1 start
6
8
7
9

Then 'end' reaches -1 with no further swapping (because nums[start] contains the minimum element), leaving the beginning region sorted. Then the loop restarts, with 'start' incremented.

2
3
4
5
1
6 start
8
7
9 end

And it happens all over again...

Oh, Ok. I see what's happening now. You have to start the first loop at zero, and end at a value one less than the size, and for the inner loop start at 1, end at zero. However, I would have never caught that without you guys.
Thanks for all the help!

Dragon, thanks for showing a better alogorithm, and rash, thanks for such a detailed explanation of what I was doing wrong.

This article has been dead for over six months. Start a new discussion instead.