DaniWeb Forum Index > Software Development > C++

C++ RSS

sorting algorithm not working correctly

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Jun 2004

Posts: 2,108

Reputation: server_crash is on a distinguished road

Solved Threads: 18

server_crash server_crash is offline

Offline

Postaholic

sorting algorithm not working correctly

Oct 28th, 2005

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

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#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;
             }
         }
     }
}
#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?

•

Join Date: Aug 2005

Posts: 15,379

Reputation: Ancient Dragon has a reputation beyond repute

Solved Threads: 1466

Ancient Dragon Ancient Dragon is online now

Online

Still Learning

Re: sorting algorithm not working correctly

Oct 28th, 2005

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.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
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;
             }
         }
     }
}
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;
             }
         }
     }
}

•

Join Date: Jun 2005

Posts: 2,039

Reputation: Rashakil Fol is just really nice

Solved Threads: 139

Rashakil Fol Rashakil Fol is offline

Offline

Super Senior Demiposter

Re: sorting algorithm not working correctly

Oct 28th, 2005

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
             if (nums[start] > nums[end])
             {
                 int temp = nums[start];
                 nums[start] = nums[end];
                 nums[end] = temp;
             }
             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:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
2
3
4
1
7  start
6
8
5
9 end
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.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
2
3
4
1
5 start
6  ^
8  |
7 end
9
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.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
2
3
4
5 end (after swapping)
1 start
6
8
7
9
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.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
2
3
4
5
1
6 start
8
7
9 end
2
3
4
5
1
6 start
8
7
9 end

And it happens all over again...

All my posts may be redistributed under the GNU Free Documentation License.

•

Join Date: Jun 2004

Posts: 2,108

Reputation: server_crash is on a distinguished road

Solved Threads: 18

server_crash server_crash is offline

Offline

Postaholic

Re: sorting algorithm not working correctly

Oct 29th, 2005

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.