Selection Sort is a simple comparison-based sorting algorithm. Its main idea is to repeatedly select the smallest (or largest) element from the unsorted portion of an array and move it to its correct position.
It is not the most efficient sorting algorithm for large arrays (time complexity is O(n²)), but it is easy to understand and implement.
Algorithm Steps (General)
Start at the beginning of the array. Consider the first element (i = 0) as the smallest element. Store its index in minIndex.
Compare this element with every other element to its right (j = i+1 to end of array).
If a smaller element is found, update minIndex to that element's index.
After scanning the rest of the array, the smallest element in the unsorted portion has been found.
Swap the element at i with the element at minIndex (unless i == minIndex).
Move to the next position (i++) and repeat steps 1–4 until the entire array is sorted.
Key Points
- minIndex keeps track of the position of the smallest element in the unsorted portion.
- Swapping only happens once per outer loop iteration, after the inner loop finds the minimum.
- The outer loop ensures that each position is filled with the correct smallest remaining element.
Time Complexity:
Best case: O(n²)
Worst case: O(n²)
Space Complexity: O(1) (in-place sort)
Example in Java
Let’s walk through a concrete Java example using the array:
int[] arr = {13, 12, 11, 10, 9, 33, 12};
Outer Loop i = 0 (First position)
Start: minIndex = 0 (value 13)
Inner loop comparisons:
j = 1 → compare 12 < 13 → true → minIndex = 1
j = 2 → compare 11 < 12 → true → minIndex = 2
j = 3 → compare 10 < 11 → true → minIndex = 3
j = 4 → compare 9 < 10 → true → minIndex = 4
j = 5 → compare 33 < 9 → false → minIndex = 4
j = 6 → compare 12 < 9 → false → minIndex = 4
Swap arr[0] with arr[4] → array becomes: [9, 12, 11, 10, 13, 33, 12]
Outer Loop i = 1 (Second position)
Start: minIndex = 1 (value 12)
Inner loop comparisons:
j = 2 → compare 11 < 12 → true → minIndex = 2
j = 3 → compare 10 < 11 → true → minIndex = 3
j = 4 → compare 13 < 10 → false → minIndex = 3
j = 5 → compare 33 < 10 → false → minIndex = 3
j = 6 → compare 12 < 10 → false → minIndex = 3
Swap arr[1] with arr[3] → array becomes: [9, 10, 11, 12, 13, 33, 12]
Outer Loop i = 2 (Third position)
Start: minIndex = 2 (value 11)
Inner loop comparisons:
j = 3 → compare 12 < 11 → false → minIndex = 2
j = 4 → compare 13 < 11 → false → minIndex = 2
j = 5 → compare 33 < 11 → false → minIndex = 2
j = 6 → compare 12 < 11 → false → minIndex = 2
minIndex == i → no swap
Array remains: [9, 10, 11, 12, 13, 33, 12]
Outer Loop i = 3 (Fourth position)
Start: minIndex = 3 (value 12)
Inner loop comparisons:
j = 4 → compare 13 < 12 → false → minIndex = 3
j = 5 → compare 33 < 12 → false → minIndex = 3
j = 6 → compare 12 < 12 → false → minIndex = 3
Swap arr[3] with arr[3] → array remains the same (swap with itself, optional)
Outer Loop i = 4 (Fifth position)
Start: minIndex = 4 (value 13)
Inner loop comparisons:
j = 5 → compare 33 < 13 → false → minIndex = 4
j = 6 → compare 12 < 13 → true → minIndex = 6
Swap arr[4] with arr[6] → array becomes: [9, 10, 11, 12, 12, 33, 13]
Outer Loop i = 5 (Sixth position)
Start: minIndex = 5 (value 33)
Inner loop comparisons:
j = 6 → compare 13 < 33 → true → minIndex = 6
Swap arr[5] with arr[6] → array becomes: [9, 10, 11, 12, 12, 13, 33]
Outer Loop i = 6 (Last element)
Only one element left → already sorted
Array remains: [9, 10, 11, 12, 12, 13, 33]
Key Takeaways
minIndex tracks the index of the smallest element in the remaining array.
The inner loop compares every remaining element with the current minimum.
The if (minIndex != i) check avoids unnecessary swaps.
Each outer loop iteration places the next smallest element in its correct position.
By the end, the array is fully sorted from left to right.
Top comments (0)