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

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)