Selection Sort Algorithm
Selection Sort is an in-place comparison sorting algorithm that repeatedly selects the smallest element from the unsorted region and swaps it into the next sorted position.
Difficulty: Easy · Interactive Visualizer · C++ / Python / Java / JS Code
Selection Sort Algorithm
Selection Sort divides the array into two regions: a sorted prefix on the left (initially empty) and an unsorted suffix on the right. On each pass, it scans the unsorted suffix to find the minimum element and swaps it into the first position of that suffix, growing the sorted region by one.
At a Glance
| Property | Value |
| :--- | :--- |
| Best-Case Time | $O(n^2)$ |
| Average-Case Time | $O(n^2)$ |
| Worst-Case Time | $O(n^2)$ |
| Auxiliary Space | $O(1)$ |
| In-Place? | Yes |
| Stable? | No (long-distance swaps can reorder equal elements) |
| Comparison-Based? | Yes |
| Best Used When | Array is small and memory writes/swaps are very expensive (at most $n - 1$ swaps) |
---
How It Works
1. For each position i from 0 to n - 2:
2. Assume minIdx = i.
3. Scan j from i + 1 to n - 1; whenever A[j] < A[minIdx], update minIdx = j.
4. Swap A[i] with A[minIdx] (if minIdx != i).
procedure selectionSort(A):
n = length(A)
for i = 0 to n - 2:
minIdx = i
for j = i + 1 to n - 1:
if A[j] < A[minIdx]:
minIdx = j
if minIdx != i:
swap(A[i], A[minIdx])
Step-by-Step Trace
Sorting [64, 25, 12, 22, 11]:
- Initial:
[64, 25, 12, 22, 11] - Pass 1 (
i = 0): Min in[64, 25, 12, 22, 11]is11→ swap with64→[11 | 25, 12, 22, 64] - Pass 2 (
i = 1): Min in[25, 12, 22, 64]is12→ swap with25→[11, 12 | 25, 22, 64] - Pass 3 (
i = 2): Min in[25, 22, 64]is22→ swap with25→[11, 12, 22 | 25, 64] - Pass 4 (
i = 3): Min in[25, 64]is25→ already in place →[11, 12, 22, 25 | 64] - Result:
[11, 12, 22, 25, 64]
---
Complexity & Key Insights
- Always $O(n^2)$ Comparisons: Even if the input is already sorted, Selection Sort performs $\frac{n(n - 1)}{2}$ comparisons because it must scan the entire remaining suffix to confirm the minimum.
- Minimal Writes — $O(n)$ Swaps: Unlike Bubble Sort and Insertion Sort (which can do $O(n^2)$ writes), Selection Sort performs at most $n - 1$ swaps. This makes it useful when writing to storage (such as flash memory or EEPROM) is costly.
- Why It Is Unstable: Consider
[4a, 4b, 1]. On pass 1,4aswaps with1, producing[1, 4b, 4a]— reversing the relative order of4aand4b. - When NOT to use it: For nearly sorted data, Insertion Sort runs in $O(n)$ instead of $O(n^2)$. For general large datasets, use Merge Sort, Quick Sort, or Heap Sort.
---
Practice Problems
Easy
1. Sort an Array of Integers
Given an array of integers, sort it in non-decreasing order using Selection Sort.
Approach: Find the minimum index in A[i..n-1] and swap it with A[i]. Time: $O(n^2)$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <utility>
#include <vector>
void selectionSort(std::vector<int>& arr) {
int n = static_cast<int>(arr.size());
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) {
std::swap(arr[i], arr[minIdx]);
}
}
}
int main() {
std::vector<int> arr = {64, 25, 12, 22, 11};
selectionSort(arr);
for (int x : arr) std::cout << x << " ";
std::cout << "\n";
return 0;
}
</details>
2. Sort Characters in a String
Given a string, sort its characters in ascending order using Selection Sort.
Approach: Apply Selection Sort directly to the characters of std::string. Time: $O(n^2)$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <string>
#include <utility>
void selectionSortString(std::string& s) {
int n = static_cast<int>(s.size());
for (int i = 0; i < n - 1; ++i) {
int minIdx = i;
for (int j = i + 1; j < n; ++j) {
if (s[j] < s[minIdx]) {
minIdx = j;
}
}
if (minIdx != i) {
std::swap(s[i], s[minIdx]);
}
}
}
int main() {
std::string str = "selectionsort";
selectionSortString(str);
std::cout << str << "\n";
return 0;
}
</details>
---
Intermediate
3. Find the $k$-th Smallest Element (Partial Selection Sort)
Given an array of $n$ integers and an integer $k$ ($1 \le k \le n$), find the $k$-th smallest element in $O(n \cdot k)$ time.
Approach: Run only the first $k$ outer iterations of Selection Sort. After $k$ passes, the $k$ smallest elements occupy arr[0..k-1] in sorted order, so arr[k - 1] is the answer. Time: $O(n \cdot k)$. Space: $O(1)$. (For large $k$, use Quickselect in Quick Sort.)
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <utility>
#include <vector>
int kthSmallest(std::vector<int> arr, int k) {
int n = static_cast<int>(arr.size());
for (int i = 0; i < k; ++i) {
int minIdx = i;
for (int j = i + 1; j < n; ++j) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
std::swap(arr[i], arr[minIdx]);
}
return arr[k - 1];
}
int main() {
std::vector<int> arr = {7, 10, 4, 3, 20, 15};
std::cout << "3rd smallest: " << kthSmallest(arr, 3) << "\n";
return 0;
}
</details>
4. Sort a Singly Linked List
Given the head of a singly linked list, sort its nodes in ascending order using Selection Sort.
Approach: For each node i, scan j through the remaining nodes to find the minimum value node and swap values with i. Time: $O(n^2)$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <utility>
struct Node {
int data;
Node* next;
explicit Node(int v) : data(v), next(nullptr) {}
};
void selectionSortList(Node* head) {
for (Node* i = head; i != nullptr; i = i->next) {
Node* minNode = i;
for (Node* j = i->next; j != nullptr; j = j->next) {
if (j->data < minNode->data) {
minNode = j;
}
}
std::swap(i->data, minNode->data);
}
}
void freeList(Node* head) {
while (head) {
Node* next = head->next;
delete head;
head = next;
}
}
int main() {
Node* head = new Node(4);
head->next = new Node(2);
head->next->next = new Node(1);
head->next->next->next = new Node(3);
selectionSortList(head);
for (Node* p = head; p != nullptr; p = p->next) {
std::cout << p->data << " ";
}
std::cout << "\n";
freeList(head);
return 0;
}
</details>
---
Hard
5. Stable Selection Sort on Custom Records (Deck of Cards)
Sort a deck of cards by suit (C < D < H < S) and then by rank (1..13), while preserving the relative order of cards with identical suit and rank.
Approach: Standard Selection Sort breaks stability because swapping deck[i] with deck[minIdx] jumps deck[i] over equal elements. Instead, save deck[minIdx], shift deck[i..minIdx-1] right by one slot, and place the saved card at deck[i]. Time: $O(n^2)$ comparisons and $O(n^2)$ shifts. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <vector>
struct Card {
char suit; // 'C', 'D', 'H', 'S'
int rank; // 1..13
int id; // original order tag to verify stability
};
int suitOrder(char s) {
switch (s) {
case 'C': return 0;
case 'D': return 1;
case 'H': return 2;
case 'S': return 3;
default: return 4;
}
}
bool lessCard(const Card& a, const Card& b) {
if (suitOrder(a.suit) != suitOrder(b.suit)) {
return suitOrder(a.suit) < suitOrder(b.suit);
}
return a.rank < b.rank;
}
void stableSelectionSort(std::vector<Card>& deck) {
int n = static_cast<int>(deck.size());
for (int i = 0; i < n - 1; ++i) {
int minIdx = i;
for (int j = i + 1; j < n; ++j) {
if (lessCard(deck[j], deck[minIdx])) {
minIdx = j;
}
}
Card key = deck[minIdx];
for (int j = minIdx; j > i; --j) {
deck[j] = deck[j - 1];
}
deck[i] = key;
}
}
int main() {
std::vector<Card> deck = {
{'H', 12, 1}, {'C', 5, 2}, {'D', 5, 3}, {'C', 5, 4},
{'S', 13, 5}, {'C', 12, 6}, {'D', 1, 7}, {'S', 1, 8}
};
stableSelectionSort(deck);
for (const auto& c : deck) {
std::cout << c.suit << c.rank << "(#" << c.id << ") ";
}
std::cout << "\n";
return 0;
}
</details>
---
Related Algorithms
- Heap Sort — speeds up Selection Sort from $O(n^2)$ to $O(n \log n)$ by using a binary heap to find the next extreme element in $O(\log n)$.
- Insertion Sort — naturally stable and runs in $O(n)$ on nearly sorted inputs.
- Bubble Sort — another introductory $O(n^2)$ comparison sort.