Selection Sort Algorithm

This blog post explains Selection Sort Algorithm and its implementation using the C programming language. So before writing the C code for the Selection Sort Algorithm let’s first understand the Selection Sort Algorithm.

 

What is Selection Sort Algorithm:

Selection sort is an in-place comparison sorting algorithm. It has an O(n2) time complexity, which makes it inefficient on large lists.

The selection sort algorithm sorts an array by selecting the smallest element from an unsorted list in each iteration and putting it at the beginning of the unsorted list.

The algorithm divides the input array (list) into two parts:

1. A sorted subarray of items. Initially, the sorted subarray is empty.

2. Remaining unsorted items that occupy the rest of the array. Initially, the unsorted subarray is the entire input array.

 

Selection Sort Algorithm Steps:

Let’s see the required steps to sort a list using the Selection Sort algorithm. Suppose unsorted list is (11, 25, 10, 22, 64).

1. Set the first element as a minimum:

Sorted Sublist Unsorted Sublist Least element in Unsorted list
() (11, 25, 10, 22, 64) 11

 

2. Compare minimum element with other elements:

After selecting the first elements as a minimum. Compare the minimum with the second element. If the second element is smaller than the minimum, assign the second element as minimum otherwise do nothing.

After that compare the minimum with the third element. Again, if the third element is smaller, then assign minimum to the third element otherwise do nothing. Repeat the same process until the last element.

Sorted Sublist Unsorted Sublist Least element in Unsorted list
() (11, 25, 10, 22, 64) 11
() (11, 25, 10, 22, 64) 11
() (11, 25, 10, 22, 64) 10
() (11, 25, 10, 22, 64) 10
() (11, 25, 10, 22, 64) 10

 

3. Swapping minimum with left most unsorted array element:

After each iteration, the minimum is placed in the front of the unsorted list. You can see the table now 10 swaps with 11 (left-most element of the unsorted array).

Sorted Sublist Unsorted Sublist Least element in Unsorted list
(10) (25, 11, 22, 64) 25

 

Now repeat steps 1 to 3 until all the elements of the unsorted sublist are placed in the sorted sublist.  See the below table.

Sorted sublist Unsorted sublist Least element in Unsorted list
() (11, 25, 10, 22, 64) 10
(10) (25, 11, 22, 64) 11
(10, 11) (25, 22, 64) 22
(10, 11, 22) (25, 64) 25
(10, 11, 22, 25) (64) 64
(10, 11, 22, 25, 64) ()

 

Selection Sort example code:

Now let’s see the example code for the Selection Sort Algorithm using the C programming language.

#include <stdio.h>

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void selectionSort(int arr[], int array_size)
{
    int i, j, min_idx;

    // One by one move boundary of unsorted Sublist
    for (i = 0; i < array_size-1; i++)
    {
        // Index of the minimum element in unsorted array
        // in beginning first element as minimum element
        min_idx = i;
        for (j = i+1; j < array_size; j++)
        {
            //compare unsorted element with minimum element
            if (arr[j] < arr[min_idx])
            {
                min_idx = j;
            }
        }

        //minimum is placed in the front of the unsorted list.
        swap(&arr[min_idx], &arr[i]);
    }
}

//print array element
void printArray(int arr[], int size)
{
    int i;
    for (i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}


int main()
{
    //input array
    int arr[] = {11, 25, 10, 22, 64};

    //aray size
    int array_size = sizeof(arr)/sizeof(arr[0]);

    //selection sort algorithm
    selectionSort(arr, array_size);

    printf("Sorted array: \n");

    printArray(arr, array_size);

    return 0;
}

Output:

selection sort

 

Selection Sort Complexity:

Time Complexity
Best O(n2)
Worst O(n2)
Average O(n2)
Space Complexity O(1)

 

Advantages:

  • Easy to implement.
  • In-place sort (requires no additional storage space)

Disadvantages

  • Doesn’t scale well: O(n2)

 

 

Recommended Articles for you: