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.

Previous slideNext slide

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 << " ";
}
}

Time Complexity

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

• O(n*n) for compairson.

• 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 compairson.

  • 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 compairson.

  • O(n) for swap.

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

Space Complexity

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