c++ - sorting arrays in C++

Question

1.

const int nSize=6;
int anArray[nSize]={ 30, 60, 20, 50, 40, 10 };
for(int nStartIndex=0;nStartIndex<nSize;nStartIndex++)
{
    int nSmallestIndex=nStartIndex;

    for(int nCurrentIndex=nStartIndex+1;nCurrentIndex<nSize;nCurrentIndex++)
    {
        if(anArray[nCurrentIndex]<anArray[nStartIndex])
            nSmallestIndex=nCurrentIndex;
    }

    swap(anArray[nStartIndex],anArray[nSmallestIndex]);


}

2.

const int nSize=6;
int anArray[nSize]={ 30, 60, 20, 50, 40, 10 };
for(int nStartIndex=0;nStartIndex<nSize;nStartIndex++)
{
    int nSmallestIndex=nStartIndex;

    for(int nCurrentIndex=nStartIndex+1;nCurrentIndex<nSize;nCurrentIndex++)
    {
        if(anArray[nCurrentIndex]<anArray[nSmallestIndex])
            nSmallestIndex=nCurrentIndex;
    }

    swap(anArray[nStartIndex],anArray[nSmallestIndex]);


}

why do they give different results although nSmallestIndex equals to nStartIndex?

first code results {10,30,20,40,50,60}

second code results {10,20,30,40,50,60}

score 5 · Accepted Answer

The logic in code sampe 1 is wrong and that's why it gives the wrong answer. In your second loop, you want to find the smallest element from [nStartIndex, nSize). But you only compare the current one with anArray[nStartIndex]. At the end you get nSmallestIndex equal to the last element smaller than anArray[nStartIndex].

For code sample two, the logic is right. You save the current smallest index in nSmallestIndex and use the updated version to compare in the if statement,

   if(anArray[nCurrentIndex]<anArray[nSmallestIndex])

btw, the sorting method in this code is O(N^2) which is not good generally. It is also noted by others here C++ STL has facilities to do this better and portable.

score 1 · Accepted Answer

There is a wrong condition inside your inner loop in the first example: if(anArray[nCurrentIndex]<anArray[nStartIndex]). Use nSmallestIndex instead of nStartIndex.

But in C++ you can do it in one line:

std::sort( anArray, anArray + nSize, std::less<int>() );

If you want to do it in C just use this code:

const int nSize=6;
int anArray[nSize]={ 30, 60, 20, 50, 40, 10 };

int Compare(const void* a ,const void* b)
{
    return ( *(int*)a > *(int*)b ) ? 1 : ( ( *(int*)a < *(int*)b ) ? -1 : 0 );
}

...

qsort( anArray, nSize, sizeof( int ), &Compare );

score 0 · Accepted Answer

Because nSmallestIndex equals to nStartIndex only at the begining of the second for, after some iteration nSmallestIndex can change but nSmallestIndex won't change because there are not the same variable

score 0 · Accepted Answer

The idea behind selection sort is to find the smallest/largest element and position it to a proper index

Clearly your first algo's inner for loop

for(int nCurrentIndex=nStartIndex+1;nCurrentIndex<nSize;nCurrentIndex++)
    {
        if(anArray[nCurrentIndex]<anArray[nStartIndex])
            nSmallestIndex=nCurrentIndex;
    }

Never compares with new smaller index, it just compares the iterating number with original smaller value.

Whereas in 2nd algo's inner loop

for(int nCurrentIndex=nStartIndex+1;nCurrentIndex<nSize;nCurrentIndex++)
    {
        if(anArray[nCurrentIndex]<anArray[nSmallestIndex])
            nSmallestIndex=nCurrentIndex;
    }

It updates the smallestIndex and hence correctly find the smallest value for a swap.

score 0 · Accepted Answer

why do they give different results although nSmallestIndex equals to nStartIndex?

The only difference betweent the two pieces of code:

<         if(anArray[nCurrentIndex]<anArray[nStartIndex])
---
>         if(anArray[nCurrentIndex]<anArray[nSmallestIndex])

So the conditional is different on nSmallestIndex and nStartIndex. But these values are not the same in the two pieces of code:

See the lines:

    if(anArray[nCurrentIndex]<anArray[<VALUE>])
        nSmallestIndex=nCurrentIndex;
     // ^^^^^^^^^^^^^^^   Assignment changes the value.

c++ - sorting arrays in C++

5 回答 5

Related

Reference