Selection Sort Algorithm

A in-place sorting algorithm that virtually divides an array into a sorted subarray and an unsorted subarray. Then it selects the smallest element from the unsorted subarray and swap with the first element at the the unsorted subarray in each iteration. The average and worst time complexity of selection sort is O(n²), so it is not suitable for large data sets.

selection sort summary card

Table of Contents
· How Does Selection Sort Algorithm Work?
· Graphical Explanation
· Code Implementation
  ∘ Complexity
  ∘ Pseudocode
  ∘ Golang
  ∘ Python

How Does Selection Sort Algorithm Work?

Selection sort algorithm splits an array into sorted and unsorted part. The sorted part is empty initially and the unsorted part contains the entire array.

initial state

For each iteration, the algorithm selects the minimum element from the unsorted part and swap with the leftmost element of the unsorted part. This process is continuous until the whole array is traversed.

Graphical Explanation

sorting array

selection sort process

Code Implementation

Complexity

Time: O(n²)
Space: O(1)
n: the total number of elements in the input array

Pseudocode

for currentIdx from 0 to len(array):
    smallestIdx = currentIdx
    # find the smallest element
    for j in currentIdx+1 to len(array):
        if array[smallestIdx] > array[j]:
            smallestIdx = j
    swap array[currentIdx] and array[smallestIdx]

Golang

Python

You can access the source code here.

Other sorting algorithms:

• Bubble sort algorithm
• Insertion sort algorithm
• Quick sort algorithm
• Heap sort algorithm
• Merge sort algorithm
• Counting sort algorithm
• Bucket sort algorithm
• Radix sort algorithm
• Sorting algorithms summary