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.

  • Select the index of the first element of unsorted subarray as minimum element index min.
  • Compare value at the min with the rest of the elements and reset it to this element if a smaller element is found.
  • Swap element at the min with the element at last index of sorted subarray.
  • Repeat the above step n-2 times for the rest of the elements in the unsorted subarray.

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(n2). 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 = n2

  • Worst Case

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

  • Best Case

The best-case time complexity is [Big Omega]: O(n2). 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.

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - Sort Algorithm

  • Quick Sort
  • Tree Sort