Selection Sort

1. Selection Sort Algorithm
2. Selection Sort Example
3. Selection Sort Algorithm Implementation
4. Selection Sort Algorithm Complexity

Selection sort is a simple sorting algorithm. It works by dividing the array into two parts: sorted and unsorted subarray. Selection sort finds the smallest element inside the unsorted subarray and moves it at the last index of the sorted subarray. It is used when swap operations are very costly because, at max, only n swaps are required.

Selection Sort Algorithm

Let us assume that we have an unsorted array A[] containing n elements.

Selection Sort Example

Suppose we have the array: (5,3,4,2,1,6). We will sort it using the selection sort algorithm.

• First Iteration

Minimum Element: A[4] = 1

Swap (A[4], A[0]). The array becomes : (1) (3,4,2,5,6)

• Second Iteration

Minimum Element: A[3] = 2

Swap (A[3], A[1]). The array becomes : (1,2) (4,3,5,6)

• Third Iteration

Minimum Element: A[3] = 3

Swap (A[3], A[2]). The array becomes : (1,2,3) (4,5,6)

• Fourth Iteration

Minimum Element: A[3] = 4

Swap (A[3], A[3]). The array becomes : (1,2,3,4) (5,6)

• Fifth Iteration

Minimum Element: A[4] = 5

Swap (A[4], A[4]). The array becomes : (1,2,3,4,5) (6)

The last element is already sorted. We get the sorted array as : (1,2,3,4,5,6)

Selection Sort Algorithm Implementation

#include <bits/stdc++.h>
using namespace std;

void selectionSort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    // Find the minimum element for index i
    int min = i;
    for (int j = i + 1; j < n; j++)
      if (arr[j] < arr[min]) min = j;
    // Put element in sorted position
    swap(arr[min], arr[i]);
  }
}
int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  selectionSort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Selection Sort Algorithm Complexity

Time Complexity

• Average Case

On average, n-i comparisons are made in the ith pass of insertion sort. So if there are n iterations, then the average time complexity can be given below :

(n-1) + (n-2) + (n-3) + ... + 1 = n*(n-1)/2

Hence the time complexity is of the order of [Big Theta]: O(n²). It can also be calculated by counting the number of loops. There are a total of two loops of n iterations making complexity : n*n = n²

• Worst Case

The worst-case time complexity is [Big O]: O(n²).

• Best Case

The best-case time complexity is [Big Omega]: O(n²). It is the same as worst-case time complexity.

Space Complexity

Space Complexity for the selection sort algorithm is O(1) because no extra memory other than a temporary variable is required.