Selection Sort

This page provides introduction to Selection Sort.

Overview

Selection Sort is a simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the array and swapping it with the first element of the unsorted part. It continuously shrinks the unsorted portion of the array until the entire array is sorted.

Let's sort array below, with selection sort:

$$[64, 25, 12, 22, 11]$$

Step 1

Find minimum element in whole unsorted array.

Swap it with the first index of the unsorted array.

Step 2

Find minimum element in unsorted array.

Swap it with the first index of the unsorted array.

Step 3

Find minimum element in unsorted array.

Swap it with the first index of the unsorted array.

Step 4

Find minimum element in unsorted array.

Swap it with the first index of the unsorted array.

Java

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

Complexity

Let's say there are $\text{N}$ elements in an array.

Time Complexity

We are selecting minimum element from unsorted array which takes $\text{O}(\text{N})$ for each first index of the unsorted array, so total time complexity will be:

$$\text{O}(\text{N}^2)$$

Space Complexity

Algorithm uses constant space.

$$\text{O}(1)$$

Leetcode Problem Set