Selection Sort
In this page:
Basic Idea
Selection sort divides the array into a sorted portion at the front and an unsorted portion at the back, and on each pass it finds the smallest value remaining in the unsorted portion and swaps it into the next position of the sorted portion.
Example: Basic Idea
#include <iostream>
using namespace std;
int main() {
int arr[] = {29, 10, 14, 37};
int n = 4;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) if (arr[j] < arr[minIdx]) minIdx = j;
swap(arr[i], arr[minIdx]);
}
for (int i = 0; i < n; i++) cout << arr[i] << " ";
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
int[] arr = {29, 10, 14, 37};
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) if (arr[j] < arr[minIdx]) minIdx = j;
int t = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = t;
}
System.out.println(Arrays.toString(arr));
}
}arr = [29, 10, 14, 37]
n = len(arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
print(arr)#include <stdio.h>
int main() {
int arr[] = {29, 10, 14, 37};
int n = 4;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) if (arr[j] < arr[minIdx]) minIdx = j;
int t = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = t;
}
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}Login to try C/C++/Java code in the editor
Step by Step
Each pass scans the entire unsorted portion to find its minimum value, then performs exactly one swap to place that minimum at the boundary between sorted and unsorted. This means selection sort always does at most n-1 swaps total, unlike algorithms that swap on every comparison.
Example: Step by Step
#include <iostream>
using namespace std;
int main() {
int arr[] = {29, 10, 14, 37};
int n = 4;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
cout << "Scanning " << arr[j] << endl;
if (arr[j] < arr[minIdx]) minIdx = j;
}
swap(arr[i], arr[minIdx]);
cout << "Placed " << arr[i] << " at position " << i << endl;
}
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {29, 10, 14, 37};
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
System.out.println("Scanning " + arr[j]);
if (arr[j] < arr[minIdx]) minIdx = j;
}
int t = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = t;
System.out.println("Placed " + arr[i] + " at position " + i);
}
}
}arr = [29, 10, 14, 37]
n = len(arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
print("Scanning", arr[j])
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
print("Placed", arr[i], "at position", i)#include <stdio.h>
int main() {
int arr[] = {29, 10, 14, 37};
int n = 4;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
printf("Scanning %d\n", arr[j]);
if (arr[j] < arr[minIdx]) minIdx = j;
}
int t = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = t;
printf("Placed %d at position %d\n", arr[i], i);
}
return 0;
}Login to try C/C++/Java code in the editor
Small Array
Tracing selection sort on an array like [29, 10, 14, 37] shows the sorted boundary growing by one element per pass, with each pass's single swap placing the correct next-smallest value.
Example: Small Array
#include <iostream>
using namespace std;
int main() {
int arr[] = {29, 10, 14, 37};
int n = 4;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) if (arr[j] < arr[minIdx]) minIdx = j;
swap(arr[i], arr[minIdx]);
for (int k = 0; k < n; k++) cout << arr[k] << " ";
cout << endl;
}
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {29, 10, 14, 37};
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) if (arr[j] < arr[minIdx]) minIdx = j;
int t = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = t;
System.out.println(java.util.Arrays.toString(arr));
}
}
}arr = [29, 10, 14, 37]
n = len(arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
print(arr)#include <stdio.h>
int main() {
int arr[] = {29, 10, 14, 37};
int n = 4;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) if (arr[j] < arr[minIdx]) minIdx = j;
int t = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = t;
for (int k = 0; k < n; k++) printf("%d ", arr[k]);
printf("\n");
}
return 0;
}Login to try C/C++/Java code in the editor
Practice
Because selection sort's swap count is so low, it's worth comparing against bubble sort on the same input to see that fewer swaps doesn't necessarily mean fewer comparisons — both still scan roughly the same total number of element pairs.
Example: Practice
#include <iostream>
using namespace std;
int main() {
int arr[] = {9, 3, 7, 1};
int n = 4, swaps = 0;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) if (arr[j] < arr[minIdx]) minIdx = j;
if (minIdx != i) { swap(arr[i], arr[minIdx]); swaps++; }
}
cout << "Total swaps: " << swaps;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {9, 3, 7, 1};
int n = arr.length, swaps = 0;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) if (arr[j] < arr[minIdx]) minIdx = j;
if (minIdx != i) { int t = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = t; swaps++; }
}
System.out.println("Total swaps: " + swaps);
}
}arr = [9, 3, 7, 1]
n = len(arr)
swaps = 0
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]
swaps += 1
print("Total swaps:", swaps)#include <stdio.h>
int main() {
int arr[] = {9, 3, 7, 1};
int n = 4, swaps = 0;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) if (arr[j] < arr[minIdx]) minIdx = j;
if (minIdx != i) { int t = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = t; swaps++; }
}
printf("Total swaps: %d", swaps);
return 0;
}Login to try C/C++/Java code in the editor
Summary
Selection sort runs in O(n²) time regardless of the input's initial order, since it always scans the full unsorted portion on every pass even if the array happens to already be sorted — a property that distinguishes it from bubble sort's early-exit behavior.
Example: Summary
#include <iostream>
using namespace std;
int main() {
cout << "Selection sort: O(n^2) always, but far fewer swaps than bubble sort";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Selection sort: O(n^2) always, but far fewer swaps than bubble sort");
}
}print("Selection sort: O(n^2) always, but far fewer swaps than bubble sort")#include <stdio.h>
int main() {
printf("Selection sort: O(n^2) always, but far fewer swaps than bubble sort");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 9 topics to unlock
0/9 topics done
Complete these topics first: