What is Selection Sort?

Introduction 

Most programming languages have a built-in sort function, but we need to understand the sorting algorithms to understand the code effectively. The algorithm which we are going to explore in this blog is Selection Sort. 

A selection sort algorithm sorts the elements by iterating over the entire array. It selects the smallest element from the unsorted array and swaps it with the element present at the first index.

It again finds the next smallest element from the unsorted array and swaps it with the element at the second index. This keeps going on until we achieve our resultant sorted array

Let’s understand the concept in different programming languages.  

Working Of Selection Sort

Basic algorithms are a set of instructions, which you pass in computers to make a task happen. 

A selection sort algorithm will divide its input into sorted and unsorted subarrays. Initially, our array is unsorted and as we apply selection to sort the algorithm picks an element from the unsorted section and moves it to the sorted section.

Another vital thing to remember is that it keeps the smallest element sorted at the beginning of the output array.

Here we have an unsorted array of elements:

2

11

28

19

1

Table-1

We will search for the smallest number in the entire array and swap it with the element present at the first index.

2

11

28

19

1

Table-2

We will swap 2 with 1, and then our array becomes as follows. Now we will search for the next smallest element and swap it with 11.

1

11

28

19

2

Table-3

After swapping, we get the sequence of our array as {1,2,28,19,11}. Now we will search for the next smallest element and swap it with 28.

1

2

28

19

11

Table-4

After this swap, we have our output array as:  

1

2

11

19

28

Table-5

We have all the elements in sorted order, so no further swap is required, so this is our newly sorted array.

Overview: Selection Sort

Remember, we as humans can look at an array and easily know that 1 is the smallest number, but computers cannot. They have to iterate through the entire dataset to determine which number is the smallest or the largest.

So to know how computers figure the smallest and the most significant number, let’s look at the pseudo-code.

function selectionSort(array, size)

    // Iterating over the entire array from 0 to size - 2(0 - Based Indexing) 
    for i = 0 to size - 2
        smallest = array[i]
        for j = i+1 to size - 1
            if array[j] < smallest
                smallest = array[j]
                smallest_index = j

        swap(array[i],array[smallest_index])

    return array

 

The pseudocode mentioned above conveys the working of how a code will run in the selection sort:

• It sets the smallest number to be the first element in the unsorted section of the array. Initially, the whole array is unsorted i.e the first element of the array.
• It looks through the entire unsorted section of the array and then finds the smallest number.
• It will swap the value with the item at the beginning index i.e first element of the unsorted section, which increases the size of the sorted section by 1 and at the same time decreases the size of the unsorted section by 1.

The Code – Selection Sort

Sorting algorithms take the array elements as input data, perform specific operations on those arrays and deliver sorted arrays as output. So let us have a look at how the selection sort algorithm might look in different programming languages.

Selection Sort in Java

public class selectionSort {
    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int index = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[index]) {
                    index = j;
                }
            }
            int smallNumber = arr[index];
            arr[index] = arr[i];
            arr[i] = smallNumber;
        }
    }

    public static void main(String a[]) {
        int[] arr = {11,2,1,3,4,19,28};
           
        selectionSort(arr);
        for (int i: arr) {
            System.out.print(i + " ");
        }
    }
}

Output:

[1,2,3,4,11,19,28]

 

• We will use two nested loops in this function, which keep on iterating the entire array until the smallest value is found.
   
• In the first loop which represents the sorted section of the array, we have initialized variable i = 0, which keeps on incrementing its value till the final iteration.
   
• Then a nested loop is defined with another variable j, which is equal to i+1 so that it contains the value next to the smallest value and finds the smallest value from the unsorted section of the array to place in the sorted section. Both the loops keep on iterating until the final sorted array is found.

Selection Sort in Python

def selectionSort(array, size):
    for step in range(size):
        minimum_idx = step

        for i in range(step + 1, size):

        if array[i] < array[minimum_idx]:
            minimum_idx = i

     
    (array[step], array[minimum_idx]) = (array[minimum_idx], 
array[step])


list = [11,2,28,19,7,65]
size = len(list)
selectionSort(list, size)
print(list)

Output:

[2, 7, 11, 19, 28, 65]

Selection Sort in C++

#include <iostream>
using namespace std;

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

void selectionSort(int array[], int size){
    for (int step = 0; step < size - 1; step++){
        int minimum_idx = step;
        for (int i = step + 1; i < size; i++){
            if (array[i] < array[minimum_idx])
                minimum_idx = i;
        }
        swap(&array[minimum_idx], &array[step]);
    }
}

// driver code
int main(){
    int data[] = {11, 1, 21, 28, 19, 6, 7};
    int size = sizeof(data) / sizeof(data[0]);
    selectionSort(data, size);
    for (int i = 0; i < size; i++){
        cout << data[i] << " ";
    }
}

Output:

[1,6,7,11,19,21,28]

 

There is a disadvantage in this sorting method, that even if we have a sorted array or a nearly sorted array, it will continue to run checking through all the elements in the array.

This is why the time complexity of selection sort in the worst case, best case, and the average case is the same – O(n²). This means that as the number of elements increases, running time increases at a quadratic rate. Even if we have sorted the array in the best case, we will have to go through the entire array to be sure. Therefore, the time complexity in each case is the same. 

Piling Up Selection Sort

Time Complexity	O(n²) in all the cases.
Space Complexity	O(1) as we used constant extra space.
Stable/Unstable	Unstable, as it finds the minimum element and then inserts it in its correct position by swapping with the element present at the first index.
Internal/External	Internal as the input data can be adjusted in the main memory at once.
Comparable/Non-Comparable	Yes, it is a comparable algorithm that compares elements before sorting.
Recursive/Non-Recursive	Recursive as it one by one increment sorted parts and recursively calls for remaining.

Frequently Asked Questions

Why is selection sort used?

Selection sort uses very little memory storage as it does not require any additional storage beyond the original array to store the sorted array. Also, it works efficiently when smaller arrays or data sets are taken into consideration.

Which is better: selection or insertion sort?

Insertion sort is better as it runs much more efficiently because of its time complexity when the array is sorted or almost sorted. However, insertion sort always performs O(n^2) swaps in the average and worst-case, but selection sort in every case will give O(n) swaps, this is useful when writing to memory is a costly operation.

Is bubble sort faster than selection sort?

Selection Sort is faster than bubble sort because selection sort in its worst-case uses n swaps to swap the elements, whereas bubble sort uses n(n-1)/2 swaps in the worst case to sort the elements with the number of comparisons being the same for both the algorithms in the worst case i.e n(n – 1)/2

Which is the best sorting technique?

Quicksort is one of the most efficient sorting algorithms, with its average and worst-case complexities as O(N log N) and O(n*2).

Conclusion

This blog thoroughly discussed how Selection Sort works in programming languages like Python, Java, and C++.

Unlike Bubble sort, Selection Sort might not be used to that extent. But you need to understand this to help you build your foundations. Selection sort starts by solving the smallest element first by swapping it with the element present at the first index of the unsorted array. It keeps on making these iterations until we achieve a sorted array.

You can also use CodeStudio to practice a wide range of questions to help you master your skills.

Recommended Problem - Merge K Sorted Arrays

Keep Learning, Keep Growing!