{"title":"Selection Sort","description":"","content":"Selection Sort is a simple and intuitive sorting algorithm based on the idea of repeatedly selecting the smallest element from the unsorted portion of the array and placing it in its correct position.\n\nUnlike some other algorithms, Selection Sort minimizes the number of swaps. On each pass, it scans the remaining elements, finds the minimum, and swaps it with the current position. This makes its behavior predictable and easy to trace.\n\nAlthough it is not efficient for large datasets, Selection Sort is valuable for understanding the fundamentals of sorting, especially the trade-off between comparisons and swaps.\n\nIn this chapter, you will learn how Selection Sort works step by step, how to implement it, and where it fits in the broader landscape of sorting algorithms.\n\n---\n\n# What Is Selection Sort?\n\nSelection sort is a comparison-based sorting algorithm that works by repeatedly finding the minimum element from the unsorted portion of the array and placing it at the beginning of the unsorted portion.\n\nAt any point during the algorithm, 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\nIf you have already studied bubble sort, you might wonder how selection sort is different. The key distinction lies in how they move 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. This means selection sort always does fewer swaps than bubble sort for the same input. In fact, 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^2) |\n| Early termination | Yes (if no swaps) | No |\n| Stable | Yes | No |\n\n\nThis difference matters when swaps are expensive. If you are sorting large objects where moving data is costly, selection sort's minimal number of swaps gives it a practical advantage over bubble sort.\n\n---\n\n# How It Works\n\nHere is the algorithm in plain English:\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. We only need n-1 passes because once n-1 elements are placed correctly, the last element must already be 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 key insight here is that the inner loop's only job is to find the index of the minimum element. It does not perform any swaps. The single swap happens after the inner loop finishes. This is what makes selection sort efficient in terms of write operations.\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\nNotice how clean and uniform the implementations are. The algorithm translates almost line-for-line across languages because it uses only basic array operations: comparisons, index tracking, and a single swap.\n\n\n\n\n---\n\n# Example Walkthrough\n\nLet us trace through selection sort with the array `[29, 10, 14, 37, 13]`. We will follow each pass carefully and see how the sorted region grows from left to right.\n\n### Pass 1 (i = 0)\n\nWe need to find 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\nWe search 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\nWe search 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 saves us an unnecessary swap.\n\n### Pass 4 (i = 3)\n\nWe search 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\nThe algorithm is done. After 4 passes (n - 1 = 5 - 1 = 4), all 5 elements are sorted.\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. Unlike some other algorithms, its performance does not change based on the input.\n\n\n| Case | Time Complexity | Explanation |\n|------|----------------|-------------|\n| Best | O(n^2) | Even if the array is already sorted, the algorithm still scans the unsorted region to confirm the minimum. 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 actually move elements. |\n\n\n**Exact comparison count:** In the first pass, we make n-1 comparisons. In the second pass, n-2. And so on. The total is:\n\n(n-1) + (n-2) + ... + 1 = n(n-1)/2\n\nThis is always the same, no matter what the input looks like.\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. This is the best swap count among O(n^2) sorting algorithms. |\n| Stable | No | Swapping can change the relative order of equal elements (see Interview Questions below). |\n| Adaptive | No | Does not benefit from partially sorted input. Always does the same number of comparisons. |\n\n\nThe fact that selection sort is not adaptive is one of its biggest drawbacks. Bubble sort, for example, can terminate early if no swaps occur in a pass (meaning the array is already sorted). Insertion sort runs in O(n) on nearly sorted arrays. Selection sort always does the full O(n^2) comparisons no matter what.\n\n---\n\n# When to Use Selection Sort\n\n### Good Situations\n\n- **When swaps are expensive.** If you are sorting records where each swap involves moving large chunks of memory (for example, sorting structs or objects without using pointers), selection sort minimizes the number of write operations. With at most n-1 swaps, it does far fewer writes than bubble sort or insertion sort.\n- **When memory is extremely constrained.** Selection sort uses O(1) auxiliary space. It does not allocate any extra arrays or buffers. For embedded systems or environments where every byte counts, this can matter.\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 means low constant factors and minimal overhead.\n- **When you need a simple, predictable algorithm.** Selection sort always does the same amount of work regardless of input. If you need guaranteed behavior with no surprises, its consistency can be a feature.\n\n### Bad Situations\n\n- **Large datasets.** O(n^2) time becomes impractical very 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. If you need equal elements to preserve their original relative order, use insertion sort or merge sort instead.\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. If your data is likely to be partially sorted, selection sort is a poor choice.\n- **When you need average-case efficiency.** 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.","pageType":"dsa"}

Selection Sort

Ashish Pratap Singh

Get Premium