Friday, March 1, 2013

What is selection sort? How to implement in C++?

Selection sort is like: you have face up cards and you can see all at a time. First pick up the maximum numbered card, and then choose the next best maximum number and keeping them in hand in order. Continue till all the cards exhausted. So the idea is (for increasing order sort), scan through the list of numbers and find the maximum and swap it to the last number. Now scan through remaining numbers excluding the last one to find the next best maximum. And now swap with the last number of the remaining numbers. Continue till all the numbers are done. See below example output to see the operation.
  1. Best, Average and Worst case performance are O(N^2).
  2. In-place and can be implemented as Stable.

Sample implementation of selection sort

#include <iostream>

using namespace std;
const int INPUT_SIZE = 10;

void print(int *input)
{
    for ( int i = 0; i < INPUT_SIZE; i++ )
        cout << input[i] << " ";
    cout << endl;
}

void selectionsort(int* input)
{
    for (int i=INPUT_SIZE-1;i>0;i--)
    {
        //identify which is the max from the remaining numbers.
        int maxPos = 0;
        for (int j=1;j<=i;j++)
        {
            if (input[maxPos]<input[j])
            {
                maxPos = j;
            }
        }
        // Swap it with the last of the remaining numbers.
        int tmp = input[maxPos];
        input[maxPos] = input[i];
        input[i] = tmp;
        cout << "PASS: ";
        print(input);
    }
}

int main()
{
    int input[INPUT_SIZE] = {500, 700, 800, 100, 300, 200, 900, 400, 1000, 600};
    cout << "Input: ";
    print(input);
    selectionsort(input);
    cout << "Output: ";
    print(input);
    return 0;
}

Output:-
Input: 500 700 800 100 300 200 900 400 1000 600 
PASS: 500 700 800 100 300 200 900 400 600 1000 
PASS: 500 700 800 100 300 200 600 400 900 1000 
PASS: 500 700 400 100 300 200 600 800 900 1000 
PASS: 500 600 400 100 300 200 700 800 900 1000 
PASS: 500 200 400 100 300 600 700 800 900 1000 
PASS: 300 200 400 100 500 600 700 800 900 1000 
PASS: 300 200 100 400 500 600 700 800 900 1000 
PASS: 100 200 300 400 500 600 700 800 900 1000 
PASS: 100 200 300 400 500 600 700 800 900 1000 
Output: 100 200 300 400 500 600 700 800 900 1000 

0 comments :

Post a Comment

Contact Form

Name

Email *

Message *

Back to Top