Selection Sort Algorithm in Data Structure: Code, Function & Example

What Is a Selection Sort Algorithm in Data Structure?

The selection sort algorithm is a simple sorting technique for organising a list of components in ascending or descending order. It is a comparison-based sorting algorithm that compares list components to determine their relative rank.

The selection sort algorithm works by dividing the input list into two parts: the sorted component and the unsorted component. The sorted section is initially empty, and the unsorted part contains the complete list. The method identifies the smallest (or largest, depending on the sorting order) element from the unsorted section and pushes it to the end of the sorted part every time. This step is repeated until the full list has been sorted.

Selection Sort is inefficient for large lists, with an average and worst case time complexity of O(n2). This implies that the time required to sort the list grows quadratically as the number of elements increases. It does, however, have the virtue of being simple to grasp and simple to implement.

Before strengthening advanced algorithms with upGrad’s Executive PG Program in Machine Learning & AI from IIITB, let us take you through the basics of the selection sort algorithm!

How Does the Selection Sort Algorithm Work?

The Selection Sort technique identifies the least (or greatest) element in the list’s unsorted section and places it at the end of the sorted section. This process is repeated until the full list has been sorted. The following is a detailed explanation of how the selection sort algorithm works:

Consider using Selection Sort to sort a collection of numbers in ascending order:

Input: [44, 89, 52, 12, 29, 10, 80]

Step 1:

• At first, the entire list is unsorted.
• We pick the smallest element (10) in the unsorted part of the list and swap it with the first element (44).
• The sorted half now has only one element (10), whereas the unsorted part has one less element.
• Following Step 1, the following list: [10, 89, 52, 12, 29, 44, 80]

Step 2:

• The minimum element from the remaining unsorted component (12) is found and exchanged with the unsorted part’s second element (89).
• The sorted part now has two components (10, 12), and the unsorted half has one less element.
• Following Step 2, the following list: [10, 12, 52, 89, 29, 44, 80]

Step 3:

• The minimal element from the remaining unsorted component (29) is found and exchanged with the unsorted part’s third element (52).
• The sorted part now has three elements (10, 12, 29), and the unsorted half has one less element.
• Following Step 3, the following list: [10, 12, 29, 89, 52, 44, 80]

Step 4:

• The minimum element from the remaining unsorted component (44) is found and exchanged with the unsorted part’s fourth element (89).
• The sorted part now has four elements (10, 12, 29, 44), whereas the unsorted part has one less element.
• Following Step 4, the following list: [10, 12, 29, 44, 52, 89, 80]

Step 5:

• The minimum element from the remaining unsorted part (52) is found and exchanged with the unsorted part’s fifth element (52).
• The sorted part now has five elements (10, 12, 29, 44, 52), whereas the unsorted part has one less element.
• Following Step 5, the following list: [10, 12, 29, 44, 52, 89, 80]

Step 6:

• The minimum element from the remaining unsorted part (80) is found and exchanged with the unsorted part’s sixth element (89).
• The sorted half now has six elements (10, 12, 29, 44, 52, 89), whereas the unsorted part has one less element.
• Following Step 6, the following list: [10, 12, 29, 44, 52, 80, 89]

Step 7:

• The entire list has been sorted, as there are no more elements in the unsorted section.
• [10, 12, 29, 44, 52, 80, 89] is the final sorted list.

Here’s a detailed description of  selection sort in python:

def selection_sort(array):
    m = len(array)
    for i in range(m - 1):
        # Assume the current index (i) has the minimum value
        min_index = i
        # Find the minimum element in the remaining unsorted part
        for j in range(i + 1, m):
            if array[j] < array[min_index]:
                min_index = j
        # Swap the found minimum element with the first element of the unsorted part
        array[i], array[min_index] = array[min_index], array[i]

selection sort example usage:

my_list = [68, 34, 28, 19, 22, 10, 50]
selection_sort(my_list)
print(my_list)  

Output: [10, 19, 22, 28, 34, 50, 68]

Enroll for the Machine Learning Course from the World’s top Universities. Earn Masters, Executive PGP, or Advanced Certificate Programs to fast-track your career.

Algorithm and Pseudocode of a Selection Sort Algorithm

The following is the selection sort algorithm:

• Begin with the smallest (or largest, depending on the sorting order) element.
• In the unsorted segment, compare the minimum element to the following element.
• If a smaller (or larger) element is discovered, the index of the minimum (or maximum) element is updated.
• Continue comparing and updating the minimum (or maximum) element until the unsorted segment is finished.
• Swap the identified minimum (or maximum) element with the unsorted part’s initial element.
• Move the sorted part’s boundary one element to the right to expand it.
• Steps 2-6 should be repeated until the full list is sorted.

The pseudocode of a Selection Sort Algorithm is as follows:

function selection_sort(array):
    m = length(array)
    for i = 0 to m-2:
        # Assume the current index (i) has the minimum value
        min_index = i
        # Find the minimum element in the remaining unsorted part
        for j = i + 1 to m-1:
            if array[j] < array[min_index]:
                min_index = j
        # Swap the found minimum element with the first element of the unsorted part
        swap(array[i], array[min_index])

selection sort example usage:

my_list = [69, 49, 25, 19, 20, 11, 28]
selection_sort(my_list)
print(my_list) 

Output: [11, 19, 20, 25, 28, 49, 69]

Check out upGrad’s free courses on AI.

The Complexity of Selection Sort Algorithm

The selection sort algorithm’s complexity can be measured in terms of time and space complexity:

Time Complexity: Selection Sort has an O(N2) time complexity due to the two nested loops:

• One loop to select an array element one by one = O(N)
• Another loop to compare that element to every other element in the array = O(N)
• As a result, total complexity = O(N) * O(N) = O(N*N) = O(N2)

Space Complexity: Since the selection sort algorithm sorts in place, no additional memory is required for temporary data structures. As a result, Selection Sort’s space complexity is O(1), showing that the space needed by the method is constant and does not depend on the input list’s size.

Applications of Selection Sort Algorithm

Despite its slightly dull performance in comparison to more efficient sorting algorithms, the selection sort algorithm has several useful applications as follows:

• Bubble sort is routinely outperformed by selection sort.
• When memory writes are expensive or constrained (for example, in embedded systems with limited resources), the swapping process of Selection Sort can be useful. It uses fewer swaps than other sorting algorithms, such as Bubble Sort.
• Selection sort is preferable to insertion sort in terms of the number of writes ((n) swaps versus O(n2) swaps).
• It almost always outnumbers the number of writes produced by cycle sort, despite the fact that cycle sort is theoretically best in terms of write count.
• Selection Sort is parallelisable because each iteration of the outer loop can be done individually. This characteristic may be useful in some parallel computing scenarios.

Example of Selection Sort Algorithm 

The following is the selection sort program:

#include <stdio.h>
void selection_sort(int array[], int k) {
    for (int l = 0; l < k - 1; l++) {
        int min_index = l;
        for (int m = l + 1; m < k; m++) {
            if (array[m] < array[min_index]) {
                min_index = m;
            }
        }
        int temp = array[l];
        array[l] = array[min_index];
        array[min_index] = temp;
    }
}

int main() {
    int my_list[] = {46, 74, 52, 32, 21, 13, 80};
    int k = sizeof(my_list) / sizeof(my_list[0]);
    selection_sort(my_list, k);
    printf("Sorted list: ");
    for (int l = 0; l < k; l++) {
        printf("%d ", my_list[l]);
    }
    printf("\n");
    return 0;
}

In the given selection sort code, we first implement the selection_sort function, which accepts as input an integer array of size k. The selection sort algorithm is used to sort the array in ascending order.

The main function creates a test array called my_list, sorts it using the selection_sort function, and then prints the sorted list.

When you execute the programme, it will produce the following output:

Sorted list: 13 21 32 46 52 74 80

Conclusion

The selection sort algorithm is a simple and intuitive sorting strategy that may be used in educational settings and scenarios with limited resources. Although its O(n2) time complexity makes it unsuitable for huge datasets, its basic code implementation makes it useful for teaching sorting ideas. While not appropriate for high-performance applications, Selection Sort is useful when partial sorting or parallelisation is required.

Strengthening yourself with the right courses and a collection of well-equipped equipment is set to benefit your profession in the long term. upGrad’s Executive Post Graduate Programme in Software Development – Specialisation in Full Stack Development is one such course to prepare for the growing tech world. If you want to be a full-stack developer, this programme will help you develop your front-end and back-end programming skills.