#### Sorting

Problem
Implement the Selection sort algorithm.

Solution
This algorithm is also known as in-place comparison sort algorithm and requires atmost n comparisons for an array with n elements. This algorithm works by finding the smallest element in the unsorted array arr [0 … n-1] and swapping it with the element in the first position ( index 0 ). Next, we find smallest element in the subarray
arr [1 … n-1] and swapping it with the element in second position ( index 1 ). We repeat this for rest of the array. This way after n-1 iteration, we get the final sorted array. Complexity of the algorithm is O(n2).
Consider the following array { 7, 2, 5, 3, 4 }. Let’s see how Selection sort technique works :-

First Iteration :-
{ 7, 2, 5, 3, 4 } -> { 2, 7, 5, 3, 4 } ( Smallest element found in the array [ 0 … 4 ] is 2 which is swapped with                                                           element at index 0 i.e 7 )
Second Iteration :-
{ 2, 7, 5, 3, 4 } -> { 2, 3, 5, 7, 4 } ( Smallest element found in the array [ 1 … 4 ] is 3 which is swapped with                                                           element at index 1 i.e 7 )
Third Iteration :-
{ 2, 3, 5, 7, 4 } -> { 2, 3, 4, 7, 5 } ( Smallest element found in the array [ 2 … 4 ] is 4 which is swapped with                                                           element at index 2 i.e 5 )
Fourth Iteration :-
{ 2, 3, 4, 7, 5 } -> { 2, 3, 4, 5, 7 } ( Smallest element found in the array [ 3 … 4 ] is 5 which is swapped with                                                           element at index 3 i.e 7 )

Finally, after four iterations, the array is sorted.

```#include<iostream>
using namespace std;

// Display the Array
void displayArray(int arr[], int size) {
int i;
for (i=0;i<size;i++) {
cout<<arr[i]<<" ";
}
}

// swap elements in the array
void swap(int arr[],int idx1,int idx2) {
int temp;
temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}

// selection sort
// select the min element at each iteration and store
// it successively
void selectionSort(int arr[], int size) {
int i,j;
// holds the index of min element at the start
// of each iteration
int min_idx;
for (i=0;i<(size-1);i++) {
// select the minimum element and store
// it at 'i'th index
min_idx = i;
for (j=i+1;j<size;j++) {
if (arr[min_idx] > arr[j]) {
// update the min index
min_idx = j;
}
}
if (min_idx != i) {
// put the min element in
// the index pointed by 'i'
swap(arr,min_idx,i);
}
}
}

// main
int main() {
int arr[] = {7,4,5,2,3,19,11,6,9,12,8};
int size = sizeof(arr)/sizeof(arr);
cout<<"\nOriginal Array :: ";
displayArray(arr,size);
selectionSort(arr,size);
cout<<"\nSorted Array   :: ";
displayArray(arr,size);
cout<<endl;
return 0;
}```