Selection Sorting program showing abnormal results

Question

I wrote a selection sort program in C++. I have checked and rechecked the code, but the logic is perfectly fine. But the code is not sorting the array properly:

    // Selection Sort

#include <iostream>

using namespace std;

inline void swap( int& x, int& y) {
    int temp = x;
    x = y;
    y = temp;
}

int main() {
    const int n = 10;
    int list[n];

    string line(14, '-');
    cout << '\n' << line << "\nSelection Sort\n" << line << '\n';
    cout << "Enter " << n << " elements:\n";

    for( int i = 0; i < n; ++i ) {
        cin >> list[i];
    }

    for( int i = 0; i < n-1; ++i ) {
        int small = i;
        for( int j = 1; j < n; ++j ) {
            if( list[j] < list[small] ) {
                small = j;
            }
        }
        if( list[small] < list[i] ) {
            swap( list[i], list[small]);
        }
    }

    cout << "Sorted Array:\n";
    for( int i = 0; i < n; ++i ) {
        cout << list[i] << ' ';
    }

    return 0;
}

Where am I going wrong? The algorithm of Selection sort is given here: Selection Sort- wikipedia

Sample input with 10 numbers:

7 8 9 10 11 12 13 14 15 16

Output:

7 9 10 11 12 13 14 15 8 16

Technically your program is not a valid C++ program, as C++ doesn't have variable-length arrays. If you want an "array" that you set the size of at runtime, use std::vector. — Some programmer dude
– Some programmer dude, Commented Feb 20, 2016 at 7:41
Step through this in a debugger and find out at which point exactly it's not doing what you expected it to do. — Ulrich Eckhardt
– Ulrich Eckhardt, Commented Feb 20, 2016 at 8:44

iksemyonov · Accepted Answer · 2016-02-20 07:53:19Z

2

The inner loop is surely wrong here:

for( int j = 1; j < n; ++j ) {

should be

for( int j = i+1; j < n; ++j ) {

Also, the condition at the end of the loop

if( list[small] < list[i] ) {
    swap( list[i], list[small]);
}

is excessive. It is satisfied by definition after the inner loop exits.

See: Sorting algorithms - selection sort for the pseudocode and a nicely animated demo on different kinds of data.

edited Feb 20, 2016 at 7:53

answered Feb 20, 2016 at 7:45

iksemyonov

4,1961 gold badge26 silver badges44 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Max Payne · Accepted Answer · 2016-02-20 07:53:07Z

0

In the inner loop of the sorting loop, you have written: for( int j = 1; ...)
Now, every time, the inner loop is not going from 1 to n-1, but instead is going from i+1 to n-1
So change the loop to for( int j = i+1; ...)

Also, you may change the swapping condition to small != i, but this is optional.

edited Feb 20, 2016 at 7:53

answered Feb 20, 2016 at 7:45

Max Payne

2,44819 silver badges34 bronze badges

Comments

Patrick W · Accepted Answer · 2016-02-20 08:41:52Z

0

I've inspected your code and you have a logic error for the selection sort to succeed. In the inner loop, the initialization of the inner loop is always j = 1. This should change to:

for( int j = i+1; j < n; ++j ) {
        if( list[j] < list[small] ) {
            small = j;
        }
}

~~and also change the condition value of your outer loop to i < n to ensure the loop goes from start to end.~~

edited Feb 20, 2016 at 8:41

answered Feb 20, 2016 at 8:30

Patrick W

1,5674 gold badges19 silver badges28 bronze badges

1 Comment

iksemyonov Over a year ago

i < n is not required because with i==n-1 the inner loop is going to iterate over a single element, which makes little sense.

Saad Mirza · Accepted Answer · 2016-02-20 09:36:16Z

0

The inner loop should be

  for(j=i+1;j<n;j++)
  {
    if( list[j] < list[small] ) {
        small = j;
    }
  }

And if they small is not equal to I variable then swap

  if(small != i)
  {
   swap();
  }

edited Feb 20, 2016 at 9:36

answered Feb 20, 2016 at 8:41

Saad Mirza

1,19716 silver badges23 bronze badges

10 Comments

iksemyonov Over a year ago

Wrong, see sorting-algorithms.com/selection-sort. The inner loop iterates from past-the-i element to the end of the array. The array up to i is already sorted.

Saad Mirza Over a year ago

i try this thats why i am giving ans ,there are many methods to do any code ,don't rely on only one

iksemyonov Over a year ago

The algorithm called "selection sort" is well defined. See coliru.stacked-crooked.com/a/37a59d3fda61b676: your code fails the same way as OP's.

Saad Mirza Over a year ago

why dont you try the whole code? and then tell me the difference?

Saad Mirza Over a year ago

#include<iostream> using namespace std; int main() { int arr[5],i,j,temp,min; for(i=0;i<=4;i++) { cout<<"Enter the value"<<endl; cin>>arr[i]; } cout<<endl; cout<<"Values before sorting"<<endl; for(i=0;i<=4;i++) { cout<<arr[i]<<" "; } cout<<endl; for(i=0;i<=4;i++) { min=i; for(j=0;j<=4;j++) { if(arr[j+1]>arr[min]) min=j; } if(min!=i) { temp=arr[i]; arr[i]=arr[min]; arr[min]=temp; } } cout<<"Values after sorting"<<endl; for(i=0;i<=4;i++) { cout<<arr[i]<<" "; } }

|

Collectives™ on Stack Overflow

Selection Sorting program showing abnormal results

4 Answers 4

Comments

Comments

1 Comment

10 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

1 Comment

10 Comments

Your Answer

Sign up or log in

Post as a guest

Related