# Selection Sort In C++ Tutorial With Example | C++ Selection Sort Program

Selection Sort In C++ Tutorial With Example | C++ Selection Sort Program is today’s topic. Like Bubble Sort, Selection Sort is also a sorting algorithm; especially it is an in-place comparison sort. Selection sort algorithm is based on an idea of finding the min or max element or item in the unsorted array and then putting it in its correct position in the sorted array.

Content Overview

**Selection Sort In C++ Tutorial **

Selection sort algorithm divides an array into **two parts**:

- A sorted subarray
- The unsorted sub-array, from where we have to pick the smallest element and then put it into the sorted array.

Selection sort is a very simple sorting algorithm. A selection sorting algorithm is an in-place comparison-based algorithm in which the list or an array is divided into two parts, the sorted part at the leftmost end and the unsorted part at the right most end. So, initially, the sorted part is empty, and the unsorted part is an entire list.

The smallest element is selected from an unsorted array and swapped with the leftmost element, and that element becomes the part of a sorted array. This process continues moving unsorted array boundary by the component to the right. Finally, we get the sorted values.

We will first see the algorithm, and then we will see an example of Selection Sort.

**Algorithm of Selection Sort:**

**Selection(A,N)**

**Step1: **Repeat step 2 and 3 for (k=0;k<n-1;k++)

**Step2: **Call MINIMUM(A,K,N,LOC)

**Step3: **Swap A[K] and A[LOC]

**Step4: **Exit

**MINIMUM(A,K,N,LOC)**

**Step1: **Set min=A[K] and LOC=K

**Step2: **Repeat step 3 and 4 for(i=k;i<n;i++)

**Step3: **if min>a[i]

**Step4: **set min=a[i] and LOC=i

**Step5: **Return LOC

**Explanation with an example**

So, from the algorithm what we can understand that, as said above the array is in two parts, one part is in sorted order, and another part is in unsorted order and from that unsorted order, we are finding the smallest value and putting it into sorted order list.

For example, Let’s take a list of integer:

Array Number | 12 | 10 | 86 | 4 | 13 |

Location | 0 | 1 | 2 | 3 | 4 |

**First Pass**:

When K=0; **SELECTION()** will call **MINIMUM() **and will check the smallest value from the list. So, here in the first pass, the lowest value will be 4, and the **MINIMUM()** will return the location of 4 that is **LOC=3**.

Then, **SELECTION()** will swap the value with current A[0]=12. So, after swapping the value new array will be:

Array Number | 4 | 10 | 86 | 12 | 13 |

Location | 0 | 1 | 2 | 3 | 4 |

**Second Pass**:

Now, K=1 and again** SELECTION()** will call **MINIMUM()** and the then it will check the smallest value from the unsorted array, that is 10 and then it will return the location of 10, i.e., LOC=1.

As 10 is at its correct position so the final array will be the same as it is.

**Third Pass:**

Now, K=2 and again** SELECTION()** will call **MINIMUM()** and the then it will check the smallest value from the unsorted array, that is 12, and then it will return the location of 12, i.e.,** LOC=3.**

Then, **SELECTION()** will swap the value with current A[2]=86. So, after swapping the value new array will be:

Array Number | 4 | 10 | 12 | 86 | 13 |

Location | 0 | 1 | 2 | 3 | 4 |

**Fourth Pass:**

Now, K=3 and again** SELECTION()** will call **MINIMUM()** and the then it will check the smallest value from the unsorted array, that is 13, and then it will return the location of 13, i.e.,** LOC=4**.

Then, **SELECTION()** will swap the value with current A[3]=86. So, after swapping the value new array will be:

Array Number | 4 | 10 | 12 | 13 | 86 |

Location | 0 | 1 | 2 | 3 | 4 |

**Selection Sort Pseudocode**

procedure selection sort list : array of items n : size of list for i = 1 to n - 1 /* set current element as minimum*/ min = i /* check the element to be minimum */ for j = i+1 to n if list[j] < list[min] then min = j; end if end for /* swap the minimum element with the current element*/ if indexMin != i then swap list[min] and list[i] end if end for end procedure

**C++ Program of Selection Sort**

See the below code of the **selection.cpp.**

#include<bits/stdc++.h> using namespace std; int minimum(int a[],int n, int k, int loc) { loc=k; int min=a[k]; for(int i=k;i<n;i++) { if(a[i]<min) { min=a[i]; loc=i; } } return loc; } int selection(int a[],int n) { int loc=-1,k; for(k=0;k<n-1;k++) { int loc1=minimum(a,n,k,loc); int temp=a[k]; a[k]=a[loc1]; a[loc1]=temp; } cout<<"The sorted list is:\n"; for(k=0;k<n;k++) cout<<a[k]<<" "; } int main() { int n; cout<<"Enter the size of the array: "; cin>>n; int a[n],i; cout<<"Enter the array values:\n"; for(i=0;i<n;i++) { cin>>a[i]; } //calling selection function selection(a,n); return 0; }

**Output:**

**Time Complexity:**

If we want to find the minimum element from the array of N elements, N−1 comparisons are required. After putting the minimum item in its proper position, the size of an unsorted array reduces to N−1, and then N−2 comparisons are necessary to find the minimum in the unsorted array.

Therefore (N−1) + (N−2) + ……. + 1 = (N⋅(N−1))/2 comparisons and N swaps result in the overall complexity of O(N2).

So, the time complexity for selection sort is **O(n ^{2})** as there are two nested loops.

**Auxiliary Space: O(1)**

The good thing about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation.

Conclusively, Selection Sort In C++ Tutorial With Example | C++ Selection Sort Program is over.