{"title":"Selection Sort","description":"","content":"Selection Sort is a sorting algorithm based on repeatedly selecting the smallest element from the unsorted portion of the array and placing it in its correct position.\n\nOn each pass, the algorithm scans the remaining elements, finds the minimum, and swaps it with the current position. This produces at most one swap per pass, which is far fewer writes than bubble sort performs on the same input.\n\n\n\n\n\nAlthough it is not efficient for large datasets, Selection Sort illustrates the trade-off between comparisons and swaps clearly, which makes it useful for understanding how sorting algorithms differ.\n\nThis chapter covers how Selection Sort works, how to implement it across multiple languages, and where it fits among other sorting algorithms.\n\n---\n\n# What Is Selection Sort?\n\nSelection sort is a comparison-based algorithm. At any point during the sort, the array is divided into two regions:\n\n1. **Sorted region** (left side): contains elements that are already in their final sorted positions.\n2. **Unsorted region** (right side): contains elements that still need to be processed.\n\n\n```mermaid\nflowchart LR\n subgraph SORTED[\"Sorted Region\"]\n A[\"3\"]\n B[\"5\"]\n C[\"8\"]\n end\n\n subgraph UNSORTED[\"Unsorted Region\"]\n D[\"29\"]\n E[\"14\"]\n F[\"10\"]\n G[\"37\"]\n end\n\n SORTED --> UNSORTED\n\n style A fill:#69db7c,stroke:#000,color:#000\n style B fill:#69db7c,stroke:#000,color:#000\n style C fill:#69db7c,stroke:#000,color:#000\n style D fill:#ffa94d,stroke:#000,color:#000\n style E fill:#ffa94d,stroke:#000,color:#000\n style F fill:#ffa94d,stroke:#000,color:#000\n style G fill:#ffa94d,stroke:#000,color:#000\n```\n\n\nIn each pass, the algorithm selects the smallest element from the unsorted region and swaps it with the first element of the unsorted region. This grows the sorted region by one element and shrinks the unsorted region by one.\n\n### How It Differs from Bubble Sort\n\nSelection sort and bubble sort take different approaches to moving elements into position.\n\n**Bubble sort** repeatedly compares adjacent elements and swaps them if they are out of order. It performs many swaps per pass, bubbling the largest element to the end.\n\n**Selection sort** scans the entire unsorted portion to find the minimum, then performs exactly one swap per pass. Selection sort always does fewer swaps than bubble sort for the same input. Selection sort performs at most n-1 swaps for an array of n elements, while bubble sort can perform as many as O(n^2) swaps.\n\n\n| Property | Bubble Sort | Selection Sort |\n|----------|-------------|----------------|\n| Swaps per pass | Up to n-1 | Exactly 1 |\n| Total swaps (worst case) | O(n^2) | O(n) |\n| Comparison count | O(n^2) (O(n) best case with early termination) | O(n^2) |\n| Early termination | Yes (if no swaps) | No |\n| Stable | Yes | No |\n\n\nThis difference matters when swaps are expensive. Sorting large objects where moving data is costly favors selection sort because of its minimal number of swaps.\n\n---\n\n# How It Works\n\nThe algorithm has five steps:\n\n1. Start with the first position (index 0) as the current position.\n2. Scan the entire unsorted region (from the current position to the end) to find the index of the minimum element.\n3. Swap the minimum element with the element at the current position.\n4. Move the current position one step to the right (the sorted region grows by one).\n5. Repeat steps 2-4 until the current position reaches the second-to-last element.\n\nAfter n-1 passes, every element is in its correct sorted position. The algorithm needs only n-1 passes because once n-1 elements are placed correctly, the last element is already in the right spot.\n\n\n```mermaid\nflowchart TD\n START([Start]) --> INIT[\"Set i = 0\"]\n INIT --> CHECK{\"i < n - 1?\"}\n CHECK -- No --> DONE([Array is sorted])\n CHECK -- Yes --> MIN[\"Set minIndex = i\"]\n MIN --> INNER[\"Set j = i + 1\"]\n INNER --> JCHECK{\"j < n?\"}\n JCHECK -- No --> SWAP[\"Swap arr[i]
with arr[minIndex]\"]\n JCHECK -- Yes --> COMPARE{\"arr[j] < arr[minIndex]?\"}\n COMPARE -- Yes --> UPDATE[\"minIndex = j\"]\n COMPARE -- No --> INCJ[\"j = j + 1\"]\n UPDATE --> INCJ\n INCJ --> JCHECK\n SWAP --> INCI[\"i = i + 1\"]\n INCI --> CHECK\n\n style START fill:#00ceff,stroke:#000,color:#000\n style DONE fill:#69db7c,stroke:#000,color:#000\n style INIT fill:#38d9a9,stroke:#000,color:#000\n style CHECK fill:#ffd43b,stroke:#000,color:#000\n style MIN fill:#ffa94d,stroke:#000,color:#000\n style INNER fill:#ffa94d,stroke:#000,color:#000\n style JCHECK fill:#ffd43b,stroke:#000,color:#000\n style COMPARE fill:#ffd43b,stroke:#000,color:#000\n style UPDATE fill:#ff8787,stroke:#000,color:#000\n style INCJ fill:#38d9a9,stroke:#000,color:#000\n style SWAP fill:#00ceff,stroke:#000,color:#000\n style INCI fill:#38d9a9,stroke:#000,color:#000\n```\n\n\nThe inner loop's only job is to find the index of the minimum element. It does not perform any swaps. The single swap happens once, after the inner loop finishes, which keeps the write count low.\n\n---\n\n# Code Implementation\n\n\n```java\npublic class SelectionSort {\n public static void selectionSort(int[] arr) {\n int n = arr.length;\n\n for (int i = 0; i < n - 1; i++) {\n // Find the index of the minimum element in the unsorted region\n int minIndex = i;\n for (int j = i + 1; j < n; j++) {\n if (arr[j] < arr[minIndex]) {\n minIndex = j;\n }\n }\n\n // Swap the minimum element with the first unsorted element\n if (minIndex != i) {\n int temp = arr[i];\n arr[i] = arr[minIndex];\n arr[minIndex] = temp;\n }\n }\n }\n}\n```\n\n```python\ndef selection_sort(arr):\n n = len(arr)\n\n for i in range(n - 1):\n # Find the index of the minimum element in the unsorted region\n min_index = i\n for j in range(i + 1, n):\n if arr[j] < arr[min_index]:\n min_index = j\n\n # Swap the minimum element with the first unsorted element\n if min_index != i:\n arr[i], arr[min_index] = arr[min_index], arr[i]\n```\n\n```cpp\n#include \n#include \n\nvoid selectionSort(std::vector& arr) {\n int n = arr.size();\n\n for (int i = 0; i < n - 1; i++) {\n // Find the index of the minimum element in the unsorted region\n int minIndex = i;\n for (int j = i + 1; j < n; j++) {\n if (arr[j] < arr[minIndex]) {\n minIndex = j;\n }\n }\n\n // Swap the minimum element with the first unsorted element\n if (minIndex != i) {\n std::swap(arr[i], arr[minIndex]);\n }\n }\n}\n```\n\n```go\npackage main\n\nfunc selectionSort(arr []int) {\n\tn := len(arr)\n\n\tfor i := 0; i < n-1; i++ {\n\t\t// Find the index of the minimum element in the unsorted region\n\t\tminIndex := i\n\t\tfor j := i + 1; j < n; j++ {\n\t\t\tif arr[j] < arr[minIndex] {\n\t\t\t\tminIndex = j\n\t\t\t}\n\t\t}\n\n\t\t// Swap the minimum element with the first unsorted element\n\t\tif minIndex != i {\n\t\t\tarr[i], arr[minIndex] = arr[minIndex], arr[i]\n\t\t}\n\t}\n}\n```\n\n```csharp\npublic class SelectionSort\n{\n public static void Sort(int[] arr)\n {\n int n = arr.Length;\n\n for (int i = 0; i < n - 1; i++)\n {\n // Find the index of the minimum element in the unsorted region\n int minIndex = i;\n for (int j = i + 1; j < n; j++)\n {\n if (arr[j] < arr[minIndex])\n {\n minIndex = j;\n }\n }\n\n // Swap the minimum element with the first unsorted element\n if (minIndex != i)\n {\n int temp = arr[i];\n arr[i] = arr[minIndex];\n arr[minIndex] = temp;\n }\n }\n }\n}\n```\n\n```rust\npub struct SelectionSort;\n\nimpl SelectionSort {\n pub fn selection_sort(arr: &mut Vec) {\n let n = arr.len();\n\n for i in 0..n.saturating_sub(1) {\n // Find the index of the minimum element in the unsorted region\n let mut min_index = i;\n for j in (i + 1)..n {\n if arr[j] < arr[min_index] {\n min_index = j;\n }\n }\n\n // Swap the minimum element with the first unsorted element\n if min_index != i {\n arr.swap(i, min_index);\n }\n }\n }\n}\n```\n\n```javascript\nfunction selectionSort(arr) {\n const n = arr.length;\n\n for (let i = 0; i < n - 1; i++) {\n // Find the index of the minimum element in the unsorted region\n let minIndex = i;\n for (let j = i + 1; j < n; j++) {\n if (arr[j] < arr[minIndex]) {\n minIndex = j;\n }\n }\n\n // Swap the minimum element with the first unsorted element\n if (minIndex !== i) {\n [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];\n }\n }\n}\n```\n\n```typescript\nfunction selectionSort(arr: number[]): void {\n const n = arr.length;\n\n for (let i = 0; i < n - 1; i++) {\n // Find the index of the minimum element in the unsorted region\n let minIndex: number = i;\n for (let j = i + 1; j < n; j++) {\n if (arr[j] < arr[minIndex]) {\n minIndex = j;\n }\n }\n\n // Swap the minimum element with the first unsorted element\n if (minIndex !== i) {\n [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];\n }\n }\n}\n```\n\n\nThe implementation uses only basic array operations: comparisons, index tracking, and a single swap per pass.\n\n\n\n\n\n---\n\n# Example Walkthrough\n\nTrace selection sort on the array `[29, 10, 14, 37, 13]`, watching the sorted region grow from left to right.\n\n### Pass 1 (i = 0)\n\nFind the minimum element in the entire array (indices 0 through 4).\n\n\n```shell\n[29, 10, 14, 37, 13]\n ^ current position (i = 0)\n\nScan: 29, 10, 14, 37, 13\nMinimum found: 10 at index 1\n\nSwap arr[0] and arr[1]: swap 29 and 10\n```\n\n\n**Array after Pass 1:** `[10, 29, 14, 37, 13]`\n\nThe element 10 is now in its final sorted position.\n\n### Pass 2 (i = 1)\n\nSearch the unsorted region (indices 1 through 4) for the minimum.\n\n\n```shell\n[10 | 29, 14, 37, 13]\n ^ current position (i = 1)\n\nScan: 29, 14, 37, 13\nMinimum found: 13 at index 4\n\nSwap arr[1] and arr[4]: swap 29 and 13\n```\n\n\n**Array after Pass 2:** `[10, 13, 14, 37, 29]`\n\nNow both 10 and 13 are in their final positions.\n\n### Pass 3 (i = 2)\n\nSearch the unsorted region (indices 2 through 4) for the minimum.\n\n\n```shell\n[10, 13 | 14, 37, 29]\n ^ current position (i = 2)\n\nScan: 14, 37, 29\nMinimum found: 14 at index 2\n\nminIndex == i, so no swap needed.\n```\n\n\n**Array after Pass 3:** `[10, 13, 14, 37, 29]`\n\nThe element 14 was already in the correct position. The `if (minIndex != i)` check skips the unnecessary swap.\n\n### Pass 4 (i = 3)\n\nSearch the unsorted region (indices 3 through 4) for the minimum.\n\n\n```shell\n[10, 13, 14 | 37, 29]\n ^ current position (i = 3)\n\nScan: 37, 29\nMinimum found: 29 at index 4\n\nSwap arr[3] and arr[4]: swap 37 and 29\n```\n\n\n**Array after Pass 4:** `[10, 13, 14, 29, 37]`\n\nAfter 4 passes (n - 1 = 4 for n = 5), all 5 elements are in their final positions.\n\n### Visual Summary\n\nHere is the complete sorting process at a glance:\n\n\n```mermaid\nflowchart TD\n P0[\"Initial: [29, 10, 14, 37, 13]\"]\n P1[\"Pass 1: [10, 29, 14, 37, 13]
Swapped 29 and 10\"]\n P2[\"Pass 2: [10, 13, 14, 37, 29]
Swapped 29 and 13\"]\n P3[\"Pass 3: [10, 13, 14, 37, 29]
No swap needed\"]\n P4[\"Pass 4: [10, 13, 14, 29, 37]
Swapped 37 and 29\"]\n RESULT[\"Sorted: [10, 13, 14, 29, 37]\"]\n\n P0 --> P1 --> P2 --> P3 --> P4 --> RESULT\n\n style P0 fill:#ffa94d,stroke:#000,color:#000\n style P1 fill:#00ceff,stroke:#000,color:#000\n style P2 fill:#00ceff,stroke:#000,color:#000\n style P3 fill:#00ceff,stroke:#000,color:#000\n style P4 fill:#00ceff,stroke:#000,color:#000\n style RESULT fill:#69db7c,stroke:#000,color:#000\n```\n\n\n---\n\n# Complexity Analysis\n\nSelection sort has a straightforward complexity profile. Its performance does not change based on the input.\n\n\n| Case | Time Complexity | Explanation |\n|------|----------------|-------------|\n| Best | O(n^2) | Even on an already sorted array, the algorithm still scans the unsorted region to find the minimum on every pass. There is no early termination. |\n| Average | O(n^2) | The number of comparisons is always the same regardless of element ordering. |\n| Worst | O(n^2) | Same number of comparisons as the best case. The only difference is whether swaps move elements. |\n\n\n**Exact comparison count:** Pass 1 makes n-1 comparisons. Pass 2 makes n-2. And so on. The total is:\n\n(n-1) + (n-2) + ... + 1 = n(n-1)/2\n\nThis count is the same for every input.\n\n\n| Metric | Value | Notes |\n|--------|-------|-------|\n| Space complexity | O(1) | Only uses a few extra variables (minIndex, temp). Sorts in place. |\n| Number of swaps | O(n) | At most n-1 swaps (one per pass), which is near-optimal for in-place comparison sorting. |\n| Stable | No | The single long-distance swap per pass can leap an equal element over its earlier duplicate. |\n| Adaptive | No | Does not benefit from partially sorted input. Always does the same number of comparisons. |\n\n\nThe lack of adaptiveness is a notable drawback. Bubble sort can terminate early if no swaps occur in a pass. Insertion sort runs in O(n) on nearly sorted arrays. Selection sort always does the full O(n^2) comparisons regardless of input.\n\n### Stability\n\nSelection sort is not stable. The single swap per pass can move an element over equal elements that lie between its current position and the position of the minimum, which breaks the original relative order.\n\nConsider the array `[5a, 3, 5b, 1]`, where `5a` and `5b` are two records with the same key. The first pass finds the minimum (`1` at index 3) and swaps it with `arr[0]`, producing `[1, 3, 5b, 5a]`. The original `5a, 5b` ordering is reversed.\n\nA linked-list variant that detaches and reinserts nodes (rather than swapping array slots) can preserve stability, but the standard array implementation cannot.\n\n---\n\n# When to Use Selection Sort\n\n### Good Situations\n\n- **When swaps are expensive.** Sorting records where each swap involves moving large chunks of memory (for example, sorting structs or objects without using pointers) favors selection sort because it minimizes write operations. With at most n-1 swaps, it does far fewer writes than bubble sort or insertion sort.\n- **When memory is tightly constrained.** Selection sort uses O(1) auxiliary space and allocates no extra arrays or buffers, which matters in embedded systems with strict memory budgets.\n- **Small arrays (n < 20).** For tiny arrays, the overhead of more sophisticated algorithms like quicksort or merge sort is not worth it. Selection sort's simplicity keeps constant factors low.\n- **When predictability matters.** Selection sort always does the same amount of work regardless of input, which gives it consistent timing across inputs.\n\n### Bad Situations\n\n- **Large datasets.** O(n^2) time becomes impractical quickly. Sorting 10,000 elements requires roughly 50 million comparisons. For anything beyond a few hundred elements, use O(n log n) algorithms like merge sort or quicksort.\n- **When stability is required.** Selection sort is not stable. Use insertion sort or merge sort when equal elements must preserve their original relative order.\n- **Nearly sorted arrays.** Selection sort does not benefit from existing order in the array. Insertion sort, by contrast, runs in nearly O(n) time on almost-sorted data. Selection sort underperforms on partially sorted inputs.\n- **When average-case efficiency matters.** Even among O(n^2) algorithms, insertion sort tends to outperform selection sort on average because it does fewer comparisons on random data and adapts to partial order.\n\n---\n\n# Quiz","pageType":"dsa"}

Selection Sort

Get Premium