ALKO

Selection sort

Overview

Selection sort is a simple sorting algorithm that finds the smallest element in the unsorted part of the list and swaps it with the first unsorted element.

Visualization

99
55
77
1010
22
Input
Input size n=5n=5:
99
55
77
1010
22
AA
Step 0/24

Pseudocode

Algorithm Selection Sort
1:
procedure SelectionSort(A)(A)
2:
i←0i \gets 0
3:
while i<∣A∣i \lt |A| do
4:
j,k←ij, k \gets i
5:
while j<∣A∣j \lt |A| do
6:
if A[j]>A[k]A[j] > A[k] then
7:
j←j+1j \gets j + 1
8:
else
9:
k←jk \gets j
10:
Swap(A[i],A[k])(A[i], A[k])

Time Complexity

Selection sort has the same time complexity regardless of the input. It takes (n−1)+(n−2)+…+1=(n−1)+12(n-1) + (n-2) + \ldots + 1 = \frac{(n-1) + 1}{2} comparisons to find the smallest element and n−1n - 1 swaps, resulting in a time complexity of (n−1)+12(n−1)=O(n2)\frac{(n-1) + 1}{2}(n-1) = O(n^2).