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] = large
3. 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)

1 comment: