Selection Sort

In selection sort, the smallest value among the unsorted elements of the array is selected in every pass and inserted to its appropriate position into the array. It is also the simplest algorithm. It is an in-place comparison sorting algorithm. In this algorithm, the array is divided into two parts, first is sorted part, and another one is the unsorted part. Initially, the sorted part of the array is empty, and unsorted part is the given array. Sorted part is placed at the left, while the unsorted part is placed at the right.

In selection sort, the first smallest element is selected from the unsorted array and placed at the first position. After that second smallest element is selected and placed in the second position. The process continues until the array is entirely sorted.

We assume that the first card is already sorted then, we select an unsorted card. If the unsorted card is greater than the card in hand, it is placed on the right otherwise, to the left. In the same way, other unsorted cards are taken and put in their right place.

We have an array {6, 3, 8, 12, 9} in this array the smallest element is 3. So we will place 3 at the first position, after this the array will look like {3, 6, 8, 12, 9}. Now we will again find the smallest number but this time we will not consider 3 in our search because it is in its place. Finding the next smallest element that is 6, creating an array with 6 at the second position and then again searching in the array till the array is sorted.

The average and worst-case complexity of selection sort is O(n2), where n is the number of items. Due to this, it is not suitable for large data sets.

Selection sort is generally used when -

A small array is to be sorted.
Swapping cost doesn't matter.
It is compulsory to check all elements.

Working

Set the first element as minimum.
Compare minimum with the second element. If the second element is smaller than minimum, assign the second element as minimum.
Compare minimum with the third element. Again, if the third element is smaller, then assign minimum to the third element otherwise do nothing. The process goes on until the last element.
After each iteration, minimum is placed in the front of the unsorted list.
For each iteration, indexing starts from the first unsorted element. Step 1 to 3 are repeated until all the elements are placed at their correct positions.

Algorithm

    SELECTION SORT(arr, n)  
        
    Step 1: Repeat Steps 2 and 3 for i = 0 to n-1  
    Step 2: CALL SMALLEST(arr, i, n, pos)  
    Step 3: SWAP arr[i] with arr[pos]  
    [END OF LOOP]  
    Step 4: EXIT  
        
    SMALLEST (arr, i, n, pos)  
    Step 1: [INITIALIZE] SET SMALL = arr[i]  
    Step 2: [INITIALIZE] SET pos = i  
    Step 3: Repeat for j = i+1 to n  
    if (SMALL > arr[j])  
        SET SMALL = arr[j]  
    SET pos = j  
    [END OF if]  
    [END OF LOOP]  
    Step 4: RETURN pos

Program using C

//SELECTION SORT
#include <stdio.h>  
  
    void selection(int arr[], int n)  
    {  
        int i, j, small;  
          
        for (i = 0; i < n-1; i++)    // One by one move boundary of unsorted subarray  
        {  
            small = i; //minimum element in unsorted array  
              
            for (j = i+1; j < n; j++)  
            if (arr[j] < arr[small])  
                small = j;  
    // Swap the minimum element with the first element  
        int temp = arr[small];  
        arr[small] = arr[i];  
        arr[i] = temp;  
        }  
    }  
      
    void printArr(int a[], int n) /* function to print the array */  
    {  
        int i;  
        for (i = 0; i < n; i++)  
            printf("%d ", a[i]);  
    }  
      
    int main()  
    {  
        int a[] = { 12, 31, 25, 8, 32, 17 };  
        int n = sizeof(a) / sizeof(a[0]);  
        printf("Before sorting array elements are - \n");  
        printArr(a, n);  
        selection(a, n);  
        printf("\nAfter sorting array elements are - \n");    
        printArr(a, n);  
        return 0;  
    }