Selection Sort Algorithm

Last updated on July 13th, 2024 at 11:01 am

We will discuss the Selection Sort Algorithm, pseudo code, Code implementation of Selection sort in C, C++, Java, JavaScript, Python, advantages & disadvantages, and time & space complexity of Selection Sort.

1. What is Selection Sort Algorithm?

Selection Sort is an in-place sorting algorithm. It works well on small files. It is used for storing files with very large values and small keys.

The Selection Sort first selects the smallest element from the unsorted list.
Then that element is swapped with the first element in the list.
In the next step, the list size is reduced by one because one element is present at its position.
Next, the smallest element is swapped with the second element in the list, and so on.

1.1 Example for Selection Sort

Sort the given elements (29, 64, 73, 34 and 20) by using selection sort.

We have
29, 64, 73, 34, 20
After the first pass, we get
20, 64, 73, 34, 29
After the second pass, we get
20, 29, 73, 34, 64
After the third pass, we get
20, 29, 34, 73, 64
After the fourth pass, we get
20, 29, 34, 64, 73
After the fifth pass, we get
20, 29, 34, 64, 73

The sorted list is 20, 29, 34, 64, 73.

2. Pseudocode for Selection Sort

SELECTION_SORT(A) 
1. for j <- 1 to n-1 
2. smallest <- j 
3. for i <- j+1 to n 
4. if A[i] < A[smallest] 
5. smallest <- i 
6. Exchange A[j] A[smallest]

3. Code Implementation of Selection Sort

3.1 Selection Sort in C

#include <stdio.h>

void selectionSort(int arr[], int n) {
    int i, j, min_idx;
    for (i = 0; i < n-1; i++) {
        min_idx = i;
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int arr[] = {29, 64, 73, 34, 20};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

3.2 Selection Sort in C++

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    int i, j, min_idx;
    for (i = 0; i < n-1; i++) {
        min_idx = i;
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int arr[] = {29, 64, 73, 34, 20};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

3.3 Selection Sort in Java

public class SelectionSort {
    void selectionSort(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            int min_idx = i;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[min_idx])
                    min_idx = j;
            }
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String args[]) {
        int arr[] = {29, 64, 73, 34, 20};
        SelectionSort ob = new SelectionSort();
        ob.selectionSort(arr);
        System.out.print("Sorted array: ");
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

3.4 Selection Sort in JavaScript

function selectionSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n-1; i++) {
        let min_idx = i;
        for (let j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx])
                min_idx = j;
        }
        let temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

let arr = [29, 64, 73, 34, 20];
selectionSort(arr);
console.log("Sorted array: " + arr.join(" "));

3.5 Selection Sort in Python

def selectionSort(arr):
    n = len(arr)
    for i in range(n-1):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

arr = [29, 64, 73, 34, 20]
selectionSort(arr)
print("Sorted array:", arr)

4. Advantages of Selection Sort

Simple implementation.
Doesn’t require extra space other than the array being sorted.

5. Disadvantages of Selection Sort

Inefficient for large lists. Its complexity is O(n^2), where n is the number of elements.
Not adaptive. The time complexity remains the same even if the list is partially sorted.

6. Time and Space Complexity of Selection Sort

Time Complexity
Worst Case	O(n²)
Best Case	O(n²)
Average Case	O(n²)
Space Complexity
Worst Case	O(1)

FAQs

What is Selection Sort?