Selection Sort
Selection sort is like picking the shortest kid from a crowd, then the next shortest, and lining them up one by one at the front.
In this page:
Syntax
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]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
Related Topics
{# common_mistakes/chapter_summary/browser_support: on Hindi pages the
view already swaps in the hi_ translation fields (or blanks these
out if untranslated), so this renders correctly for both languages
without a lang_code check here. #}
Common Mistakes
- Swapping inside the inner loop each time a smaller item is seen instead of once after finding the minimum, which turns it into a different, slower sort.
- Storing the minimum value instead of its index, so there is nothing to swap with.
- Starting the inner loop at
iinstead ofi + 1, or looping the outer one toninstead ofn - 1.
🔒
Chapter Quiz — Complete all 9 topics to unlock
0/9 topics done
Complete these topics first: