Selection Sort

As the name suggests SELECTION SORT involves selecting an element. Now the question arises, as to how should we select this element. What is the criteria? Where should we put it? All these answers are given in the algorithm for SELECTION SORT.

In selection sort, what we do is:-

1. Start from the first position in the array.
2. Traverse the remaining array to find the smallest number
3. Swap this smallest number with the number we selected in the first place.
4. Repeat steps 2 and 3 with the next position.

Let us try to understand this algorithm with the help of this diagram.

As we can see we have an unsorted array in the first step. The red blocks represent sorted elements and the blue elements represent the sorted ones.

• We start with the element 7 and then scan the remaining array for the minimum element.
• 1 is the minimum element and thus we swap 1 and 7.
• Now we start with the second element that is 4, and scan the remaining array for the minimum element.
• 2 is the minimum element and thus we swap 2 and 4.
• Similarly we swap 5 and 4
• This process continues and finally our complete array is sorted.

Here is an implementation of the above algorithm.

Code:

#include<stdio.h>

// function to swap two integers
void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

//defining a function to perform selection sort on array arr[] of given size
void selectionSort(int arr[], int size)
{
    int i,j;

    for(i = 0; i < size; i++)
    {
        //a variable to store the position with minimum element
        int min_pos = i;

        //we need to check the remaining elements
        for(j = i + 1; j < size; j++)
        {
            //compare each element and get the minimum element's position
            if(arr[j] < arr[min_pos])
            {
                min_pos = j;
            }
        }

        //now 'min_pos' contains the position with minimum element
        //so we swap the elements
        swap(&arr[i], &arr[min_pos]);
    }
}

// driver function to test the above function
int main(void)
{
    int i;
    int arr[10] = {3, 4, 7, 1, 10, 8, 2, 22, 99, 50};

    selectionSort(arr,10);

    printf("SORTED array:- ");
    for(i = 0; i < 10; i++)
        printf("%d ",arr[i]);

    return 0;
}
Code language: C++ (cpp)

Time Complexity: O(n^2)
Space Complexity: O(1)

The run-time of this algorithm is always O(n²) in any case. But upon analysis we can also say that this algorithm always performs swaps in the order of O(n).

Thus this type of algorithm can be helpful when we need to sort few number of elements and the cost of swapping elements is very high.

Video Explanation: