## Sunday, December 4, 2011

### Data Structure: How to implement Straight Selection Sort in C++?

In selection sort,

• In each pass smallest/largest element is selected and placed in a sorted list.
• Th entire array is divided into two parts: sorted and unsorted
• In each pass, in the unsorted subarray, the smallest element is selected and exchanged with the first element.

Algorithm

1. Declare and initialize necessary variables such as array[], i, j, large, n etc.2. for ( i = n - 1; i > 0; i--), repeat following steps       large = x[0];       index = 0;       2.1 for(j = i ; j <= i; j++)                 if x[j] > large                   large = x[i]                   index = j       2.2 x[index] =x[i]             x[i] = large3. Display the sorted array

Source Code:

#include<iostream>using namespace std;class SelectionSort{    public:        int no_of_elements;        int elements[10];    public:        void getarray();        void sortit(int [], int);        void display();};void SelectionSort::getarray(){    cout<<"How many elements? ";    cin>>no_of_elements;    cout<<"Insert array of element to sort: ";    for(int i=0;i<no_of_elements;i++){        cin>>elements[i];    }}void SelectionSort::sortit(int x[], int n){    int i, indx, j, large;    for(i = n - 1; i > 0; i--){        large = x[0];        indx = 0;        for(j = 1; j <= i; j++){            if(x[j] > large){                large = x[j];                indx = j;            }        }        x[indx] = x[i];        x[i] = large;    }}void SelectionSort::display(){    cout<<"The sorted array is :\n";    for(int i = 0 ; i < no_of_elements; i++){        cout<<elements[i]<<" ";    }    cout<<endl;}int main(){    SelectionSort SS;    SS.getarray();    SS.sortit(SS.elements,SS.no_of_elements);    SS.display();    return 0;}

Output:

How many elements? 6
Insert array of element to sort: 78 56 110 12 56 26
The sorted list is 12 26 56 56 78 110

Efficiency of Straight selection sort

In this first pass, it makes (n – 1) comparisons, in second pass it makes (n – 2) comparisons and so on, So total number of comparisons is n(n-1)/2 which is O(n^2)