sorting - I am trying to sort an array with a method similar to selection sort but my code is not working

Question

I was trying to find an alternative for the selection sort algorithm and wrote this. It's not working and I don't know why.

int main()
    {
        int size;
        cin>>size;
    
        int arr[size];
        for(int i=0; i<size; i++)
        {
            cin>>arr[i];
        }
    
        int start=0;
        int getAdd;
    
        while(start<size)
        {
            int minEl = arr[start];
    
            for (int i =start; i < size; i++)
            {
                if(arr[i]<minEl)
                {   minEl=arr[i];
                    getAdd=i;
                }
            }
    
            swap( arr[start],arr[getAdd] );
            start=start+1;
    }

This code works just fine for a size equal to 6. For a size greater than 6, it malfunctioning a little. For a size less than 6 god knows what it is.

question from:https://stackoverflow.com/questions/65872255/i-am-trying-to-sort-an-array-with-a-method-similar-to-selection-sort-but-my-code

Answer 1

The reason is that you're not giving getAdd a new value every iteration of the while loop.

This means that the for-loop inside the while loop, this one:

for (int i =start; i < size; i++)
{
    if(arr[i]<minEl)
    {   minEl=arr[i];
        getAdd=i;
    }
}

if this loop doesn't find an element that is less than minEl, which will happen in those occasions where arr[start] is already the correct element, you will re-use the previous value given to getAdd, and then swap the correctly placed element in arr[start] with another previously correctly placed element in arr[getAdd], where getAdd < start, messing up the sort order.

In the case where the first element is correctly placed, you will also probably use the uninitialized value for getAdd, which depending on your compiler and compiler settings might be an arbitrary "random" value.

This had nothing to do with 6 items by the way. My guess is that you tested it with 6 items or less that didn't have this situation. Any sized array that had no elements in the right spot already would probably be sorted correctly.

To fix this, move the declaration of getAdd into the while loop, and give it a suitable value:

int start=0;

while(start<size)
{
    int minEl = arr[start];
    int getAdd = start;

    for (int i =start; i < size; i++)

You can then also do a check before swapping:

if (start != getAdd)
    swap( arr[start],arr[getAdd] );

With the change to getAdd, you should find that your selection sort works as expected.