---
title: Selection sort
slug: selection-sort
qid: 
snapshot: enwiki-001357489530
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1357489530
tags: [23153559, 23603337, 23837581, 24623845, 24745114, 24878242, 26220375]
---

# Selection sort

> [!note] Provenance
> Snapshot `enwiki-001357489530` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1357489530> · Licensed CC BY-SA 4.0

In computer science, selection sort is an in-place comparison sorting algorithm. It has a O(n 2 ) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity and has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited. The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right. The time efficiency of selection sort is quadratic, so there are a number of sorting techniques which have better time complexity than selection sort.

In computer science, selection sort is an in-place comparison sorting algorithm. It has a O(n 2 ) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity and has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited. The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right. The time efficiency of selection sort is quadratic, so there are a number of sorting techniques which have better time complexity than selection sort. arr[] = 64 25 12 22 11 // Find the minimum element in arr[0...4] // and place it at beginning 25 12 22 64 // Find the minimum element in arr[1...4] // and place it at beginning of arr[1...4] 11 25 22 64 // Find the minimum element in arr[2...4] // and place it at beginning of arr[2...4] 11 12 25 64 // Find the minimum element in arr[3...4] // and place it at beginning of arr[3...4] 11 12 22 64 void swap(int* x, int* y) { int temp = *x; *x = *y; *y = temp; } // Selection sort function void selectionSort(int a[], int length) { // Traverse the entire array (excluding the last element) for (int i = 0; i (n-1)+(n-2)+\dots+1 = \sum_{i=1}^{n-1}i By arithmetic progression, \sum_{i=1}^{n-1}i= \frac{(n-1)+1}{2}(n-1)= \frac{1}{2}n(n-1)= \frac{1}{2}(n^2-n) which is of complexity O(n^2) in terms of number of comparisons. bingo(array A) { This procedure sorts in ascending order by repeatedly moving maximal items to the end. } begin last := length(A) - 1; { The first iteration is written to look very similar to the subsequent ones, but without swaps. } nextMax := A[last]; for i := last - 1 downto 0 do if A[i] > nextMax then nextMax := A[i]; while (last > 0) and (A[last] = nextMax) do last := last - 1; while last > 0 do begin { Each main loop searches for the new nextMax while swapping items equal to prevMax into place. } prevMax := nextMax; nextMax := A[last]; for i := last - 1 downto 0 do if A[i] > nextMax then if A[i] <> prevMax then nextMax := A[i]; else begin swap(A[i], A[last]); last := last - 1; end while (last > 0) and (A[last] = nextMax) do last := last - 1; end; end; Thus, if on average there are more than two items with the same value, bingo sort can be expected to be faster because it executes the inner loop fewer times than selection sort.
