Selection Sort

Introduction

Selection Sort is a simple comparison-based sorting algorithm that repeatedly selects the smallest (or largest) element from the unsorted portion and places it in its correct position. This process continues for multiple passes until the entire array is sorted, with the sorted section growing incrementally. While easy to implement, Selection Sort is inefficient for large datasets due to its 𝑂(𝑛2) time complexity.

How Selection Sort Works?

Multiple Passes:

Selection Sort uses several passes through the array to sort it. In each pass, the smallest (or largest) unsorted element is selected and placed in its correct position in the sorted section.

Placing Elements in Correct Positions

After the first pass, the smallest element is in its correct position (the first position of the array).
After the second pass, the second-smallest element is in its correct position (second position), and so on.

Reducing the Range

After each pass, the range of unsorted elements decreases.
Only the unsorted portion of the array is considered in subsequent passes.
After 𝑘 passes, the first 𝑘 elements are guaranteed to be in their correct positions.

Finding and Swapping

In each pass, the algorithm scans the unsorted portion to find the smallest (or largest) element.
This element is swapped with the first element of the unsorted section, ensuring it is placed in its correct position in the sorted section.

No Early Termination:

Unlike Bubble Sort, Selection Sort does not have an early termination condition. It always makes 𝑛−1 passes, even if the array becomes sorted before the final pass.

Implementation of Selection Sort

// selectionsort.cpp
#include <iostream>
#include <vector>
using namespace std;
void selectionSort(vector<int> &v)
{
    int n = v.size();
    for (int i = 0; i < n - 1; i++)
    {
        int min_idx = i;
        for (int j = i + 1; j < n; j++)
        {
            if (v[j] < v[min_idx])
            {
                min_idx = j;
            }
        }
        if (i != min_idx)
        {
            swap(v[i], v[min_idx]);
        }
    }
}
int main()
{
    vector<int> arr{9, 5, 4, 1};
    selectionSort(arr);
    for (int &ele : arr)
    {
        cout << ele << " ";
    }
}

# selection_sort.py
def selection_sort(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
        if i != min_idx:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# Example usage
arr = [9, 5, 4, 1]
selection_sort(arr)
print(arr)

// selectionSort.js
function selectionSort(arr) {
    const 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;
            }
        }
        if (i !== min_idx) {
            [arr[i], arr[min_idx]] = [arr[min_idx], arr[i]];
        }
    }
    return arr;
}

// Example usage
const arr = [9, 5, 4, 1];
selectionSort(arr);
console.log(arr);

Time Complexity

Best Case: When the array is already sorted or nearly sorted.

O(n*n) for comparison.
O(n) for swap.

Time Complexity: O(n*n)+O(n)=O(n*n)

Average Case:O(n*n), When the array is in random order.

O(n*n) for comparison.
- O(n) for swap.
Time Complexity: O(n*n)+O(n)=O(n*n)

Worst Case: O(n*n), When the array is sorted in descending order.

O(n*n) for comparison.
- O(n) for swap.
Time Complexity: O(n*n)+O(n)=O(n*n)

Space Complexity

Constant Space:O(1)
Space Complexity:O(1)

Selection Sort

On this page