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

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:**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | #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)

thanks.