Ad:

C++ Discussion Thread
Unsolved
Views: 1454

Oct 28th, 2005

sorting algorithm not working correctly

Expand Post »

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

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?

Similar Threads

Can you guys help me? about Quick Sort Algorithm in C
What is the fastest sorting algorithm? in IT Professionals' Lounge
help with sorting arrays from hightest to lowest in C++
CD-ROm isnt working correctly in Storage
sorting file in C

server_crash

Reputation Points: 113

Solved Threads: 19

Postaholic

Offline

2,108 posts
since Jun 2004

Permalink

Oct 28th, 2005

Re: sorting algorithm not working correctly

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.

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

Ancient Dragon

Sponsor

Team Colleague

Featured Poster

Reputation Points: 5608

Solved Threads: 2282

Retired and Enjoying Life

Offline

21,953 posts
since Aug 2005

Permalink

Oct 28th, 2005

Re: sorting algorithm not working correctly

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:

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.

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.

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.

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...

Rashakil Fol

Team Colleague

Reputation Points: 1135

Solved Threads: 172

Super Senior Demiposter

Offline

2,479 posts
since Jun 2005

Permalink

Oct 29th, 2005

Re: sorting algorithm not working correctly

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.

server_crash

Reputation Points: 113

Solved Threads: 19

Postaholic

Offline

2,108 posts
since Jun 2004

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: homework assignment help

Next Thread in C++ Forum Timeline: queue implementation error

DaniWeb Message

Cancel Changes

User Name
Password