0

I was trying to modify the selection sort code in c++ to check the results. My modified code is:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cout<<"Enter number of elements\n";
    cin>>n;
    int i,j,small,pos,t;
    int a[n];
    cout<<"Enter elements of array\n";
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(i=0;i<n-1;i++)
    {
        small=a[i];
        pos=i;
        for(j=i+1;j<n;j++)
        {
            if(a[j]<small)
            {
                small=a[j];
                pos=j;
            }
            t=a[i];
            a[i]=a[pos];
            a[pos]=t;
        }
    }
    cout<<"Sorted array:\n";
    for(i=0;i<n;i++)
    cout<<a[i]<<" ";
    return 0;
}

This code works for certain arrays but does not work for others. For example: If I enter 1,11,2,22,3 as the array, I get a proper output: 1,2,3,11,22. But, if I enter 1,11,2,22,3,33 as the array, I get the same array as the input as the output. Please tell me what is wrong with my code.

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
Srinjoy_Chatterjee37
  • 13
  • 4
  • [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h/31816096) – rsjaffe Jun 24 '20 at 04:24

1 Answers1

0

The issue is because of wrong place of the swap logic. The swap should be placed outside the inner loop.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cout<<"Enter number of elements\n";
    cin>>n;
    int i,j,small,pos,t;
    int a[n];
    cout<<"Enter elements of array\n";
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(i=0;i<n-1;i++)
    {
        small=a[i];
        pos=i;
        for(j=i+1;j<n;j++)
        {
            if(a[j]<small)
            {
                small=a[j];
                pos=j;
            }
        }
        //Swap here
        t=a[i];
        a[i]=a[pos];
        a[pos]=t;
    }
    cout<<"Sorted array:\n";
    for(i=0;i<n;i++)
    cout<<a[i]<<" ";
    return 0;
}

Now this gives the output as expected.

Sitesh
  • 1,816
  • 1
  • 18
  • 25
  • Yes, I was trying to see what would happen if I swapped in the 'inner' loop. Could you help me by telling me what issue is arising by swapping in the 'inner' loop? – Srinjoy_Chatterjee37 Jun 24 '20 at 04:35
  • Selection sort works by selecting the minimum element from the rest of the sub array (which is initially the complete array) and moving the smallest to the beginning by swap. You cannot perform swapping while selecting the minimum element which is wrong here. – Sitesh Jun 24 '20 at 04:53