# 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)