Selection Sort — Theory & Code
Selection Sort is one of the simplest sorting algorithms and a popular choice for learning how sorting works “under the hood.” This post goes beyond the standard explanation—covering the algorithm’s logic, visual steps, Java code, and complete performance analysis.
1. What is Selection Sort?
Selection Sort sorts an array by maintaining two regions:
- Sorted subarray (initially empty, grows from the left).
- Unsorted subarray (initially the whole array).
In each iteration, it picks the minimum element from the unsorted portion and swaps it with the element at the current boundary, thus growing the sorted part by one.:contentReference[oaicite:4]{index=4}
2. Step-by-Step Illustration
Unsorted: [64] [25] [12] [22] [11] Sorted: [] Iteration 1: Find min from unsorted → 11 Swap 11 with 64: Sorted: [11] Unsorted: [25] [12] [22] [64] Iteration 2: Find min → 12 Swap with 25: Sorted: [11][12] Unsorted: [25][22][64] Continue similarly until fully sorted.
Diagrammatic View
Pass 1: (11) [25 12 22 64] Pass 2: (11 12) [25 22 64] Pass 3: (11 12 22) [25 64] Pass 4: (11 12 22 25) [64] Pass 5: (11 12 22 25 64)
3. Java Implementation
public class SelectionSort {
public static void selectionSort(int[] arr) {
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;
}
}
// Swap the found minimum to the front
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
selectionSort(arr);
System.out.println(Arrays.toString(arr)); // [11, 12, 22, 25, 64]
}
}
4. Complexity Analysis
- Time Complexity: Always O(n²) — due to nested loops scanning the unsorted portion each pass.:contentReference[oaicite:5]{index=5}
- Space Complexity: O(1) — it's an in-place algorithm requiring minimal extra memory.:contentReference[oaicite:6]{index=6}
- Number of Swaps: Exactly n–1 swaps in worst and average cases — minimizes writes compared to other simple sorts.:contentReference[oaicite:7]{index=7}
Comparison Table
| Characteristic | Selection Sort | Remarks |
|---|---|---|
| Time Complexity | O(n²) | Same regardless of input order |
| Space Complexity | O(1) | In-place sort |
| Swaps | O(n) | Lower writes — useful for memory-sensitive contexts |
| Stability | No | Swapping may reorder equal elements |
| Adaptive? | No | Takes same time even if nearly sorted |
5. Situational Pros & Cons
- Pros:
- Simple to implement and understand.
- Minimal memory overhead (good for constrained environments).
- Few swaps — advantageous when write operations are expensive (e.g., Flash memory).:contentReference[oaicite:8]{index=8}
- Cons:
- Slow on large datasets – O(n²) time.
- Not stable — equal elements may not retain original order.
- Not adaptive — cannot leverage already sorted data.:contentReference[oaicite:9]{index=9}
6. When Should You Use It?
Ideal for:
- Educational purposes — to demonstrate basic sorting mechanics.
- Small arrays — simplicity outweighs inefficiency.
- Memory-write-constrained systems — low swap count is valuable.:contentReference[oaicite:10]{index=10}
Prefer other algorithms like Merge Sort, Quick Sort, or Heap Sort when handling large datasets due to their O(n log n) performance.:contentReference[oaicite:11]{index=11}
Conclusion
Selection Sort may not be the fastest sorting algorithm, but its clarity, minimal memory use, and predictable behavior make it a great learning tool and useful in very specific scenarios. Whether you're prepping for interviews, teaching fundamentals, or optimizing writes in embedded systems—understanding Selection Sort is a helpful step in mastering sorting algorithms.
Comments
Post a Comment