selection sort

It is a simple sorting algorithm in which array is split into two parts ,first part is sorted and an another part is unsorted . initially, the sorted part is empty and the unsorted part is the entire array. in every iteration the minimum element is selected from the unsorted array and swapped with the leftmost element in unsorted part, and that element becomes a part of the sorted array.

lets take an example:

consider an array ={9,6,16,12,5,2}

in the below figure ,green line is used to divide sorted and unsorted part

red box represents the minimum value, in every iteration.

                                               

step 1: the sorted array is empty and unsorted array has all elements, we find that the minimum element is 2 , so 2 is swapped with the leftmost element in unsorted part, and now 2 becomes a part of the sorted array.

step 2: 5 is min element ,so 5 is swapped with the leftmost element in unsorted part, and now  2,5 are part of the sorted array.

step 3: 6 is min element ,so 6 is swapped with the leftmost element in unsorted part, and now  2,5,6 are part of the sorted array.
step 4: 9 is min element ,so 9 is swapped with the leftmost element in unsorted part, and now  2,5,6,9 are part of the sorted array.

step 5:12 is min element ,so 12 is swapped with the leftmost element in unsorted part, and now  2,5,6,9,12 are part of the sorted array.

step 6: 16 is the only element in unsorted part , but as it is the only single element it will be always sorted, so now our total array is sorted  {2,5,6,9,12,16}

implementation: 

void selectionSort(int arr[], int n)  
{  
    
  
    // One by one move boundary of unsorted subarray  
    for (int i = 0; i < n-1; i++)  
    {  
        // Find the minimum element in unsorted array  
        int min = i;  
        for (int j = i+1; j < n; j++)  
        {
         if (arr[j] < arr[min])  
          {
          int min = j; 
          } 
        }
        // Swap the found minimum element with the first element  
        swap(arr[min],arr[i]);  
    }  
} 

Time Complexity: O(n*2)

Auxiliary Space: O(1)