Selection Sort Algorithm

Selection sort works by repeatedly finding the smallest element in the unsorted portion of an array and swapping it into its correct position. What sets it apart from other O(n²) algorithms is that it always makes exactly O(n) swaps regardless of the input order, making it a practical choice in scenarios where memory write operations are expensive.

This article covers how selection sort works, a full pass-by-pass dry run, Python, Java, and C++ code, a detailed complexity breakdown explaining why all three cases are O(n²), and a comparison against insertion sort and bubble sort.

Key Takeaways

What Is Selection Sort?

Selection sort is a comparison-based sorting algorithm that divides the array into two logical sub-arrays: a sorted portion on the left and an unsorted portion on the right. On every pass, it scans the entire unsorted portion to find the minimum element, then swaps that minimum with the first element of the unsorted portion. After each pass, the sorted portion grows by one and the unsorted portion shrinks by one, until the entire array is sorted.

Unlike insertion sort, which builds the sorted portion by shifting elements into place, selection sort always completes a full scan before making any move. This is both its defining characteristic and the reason its time complexity is O(n²) in every case: best, average, and worst.

This applies to selection sort directly. The algorithm is not vague or approximate. It is precisely defined, finds the exact minimum on every pass, and makes exactly the right swap every time. Its limitations come not from imprecision but from the rigid structure that precision imposes.

How Selection Sort Works

The step-by-step process:

1. Start with the full array as the unsorted portion.
2. Scan the entire unsorted portion to find the index of the minimum element.
3. Swap the minimum element with the first element of the unsorted portion.
4. Move the boundary one position to the right. The sorted portion now includes one more element.
5. Repeat from step 2 until the unsorted portion has only one element left.

Step-by-Step Dry Run: Array [19, 10, 4, 8, 3]

Here is how selection sort processes the array [19, 10, 4, 8, 3] pass by pass:

Selection Sort Algorithm

The formal algorithm in numbered steps:

1. Set the outer loop index i from 0 to n-2 (the last element falls into place automatically).
2. Assume the current position i holds the minimum. Set min_index = i.
3. Scan from i+1 to n-1. If any element is smaller than arr[min_index], update min_index.
4. After the full scan, if min_index != i, swap arr[min_index] with arr[i].
5. Increment i and repeat from step 2.

Selection Sort Pseudocode

The language-agnostic pseudocode before diving into implementations:

for i from 0 to n - 2:
    min_index = i
    for j from i + 1 to n - 1:
        if arr[j] < arr[min_index]:
            min_index = j
    if min_index != i:
        swap arr[i] and arr[min_index]

Selection Sort Code

Selection Sort in Python

The Python implementation scans for the minimum index in the inner loop and swaps only when necessary.

# Selection Sort - Python
 
def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr
 
# Example
arr = [19, 10, 4, 8, 3]
print(selection_sort(arr))
# Output: [3, 4, 8, 10, 19]

Selection Sort in Java

The Java version uses the same two-loop structure with a temporary variable for the swap.

// Selection Sort - Java
 
public class SelectionSort {
 
    static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex])
                    minIndex = j;
            }
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }
 
    public static void main(String[] args) {
        int[] arr = {19, 10, 4, 8, 3};
        selectionSort(arr);
        for (int val : arr)
            System.out.print(val + " ");
        // Output: 3 4 8 10 19
    }
}

Selection Sort in C++

The C++ implementation uses the same index-tracking approach, standard in competitive programming submissions.

// Selection Sort - C++
 
#include <iostream>
using namespace std;
 
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}
 
int main() {
    int arr[] = {19, 10, 4, 8, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    // Output: 3 4 8 10 19
    return 0;
}

Selection Sort Time and Space Complexity

The time and space complexity of selection sort across all cases:

Why are all three cases O(n²)

This is the most important thing to understand about selection sort, and the question interviewers ask most often about it. The reason all three cases are identical is structural: the algorithm has no way to skip the inner scan. To find the minimum of the unsorted portion, it must look at every element in that portion. There is no early exit condition. On pass 1 it does n-1 comparisons, on pass 2 it does n-2, and so on. Summing these gives n(n-1)/2 total comparisons, which is O(n²), regardless of whether the array is sorted, reversed, or random.

This is fundamentally different from insertion sort, which can exit its inner loop early when it finds an element smaller than the key. Selection sort has no equivalent shortcut. Finding a “minimum so far” is not the same as knowing you have found the minimum. You can only stop scanning once you have seen everything.

Is Selection Sort Stable?

No. Standard selection sort is not stable. Stability means that equal elements retain their original relative order after sorting. Selection sort violates this because it swaps the minimum element directly into the front of the unsorted portion, and that swap can move a later-occurring equal element ahead of an earlier one.

For example, consider sorting [(3a), (3b), (1)] by value, where 3a appears before 3b originally. On pass 1, the minimum is 1, and it gets swapped with 3a, giving [(1), (3b), (3a)]. The relative order of 3a and 3b has been reversed. The algorithm is not stable.

A stable variant exists: instead of swapping, shift elements forward (like insertion sort does) to place the minimum in its correct position. This preserves relative order but adds more write operations.

Selection Sort vs Insertion Sort vs Bubble Sort

Here is how selection sort compares to the two other foundational O(n²) sorting algorithms:

When to Use Selection Sort

Use selection sort when:

• Write operations are expensive. Selection sort makes at most n-1 swaps, fewer than any other simple sorting algorithm.
• The array is small. Its O(n²) cost is acceptable for datasets under 20 to 30 elements where overhead of complex algorithms is not justified.
• Memory is extremely constrained. O(1) space with minimal write overhead is hard to beat in embedded or low-resource environments.
• Simplicity of implementation matters more than speed. The two-loop structure is straightforward to write and debug correctly.

Avoid selection sort when:

• The dataset is large. O(n²) in all cases makes it impractical for thousands of elements or more.
• The data is nearly sorted. Selection sort offers no benefit on nearly sorted input, unlike insertion sort which runs in O(n).
• Stability is required. The swap-based approach disrupts the relative order of equal elements.
• You need guaranteed O(n log n) performance. Use merge sort or heapsort instead.

Advantages and Disadvantages of Selection Sort

Advantages

• Minimum number of swaps: at most n-1, regardless of input order.
• Simple to implement. The two-loop structure is easy to write correctly from scratch.
• In-place. Requires only O(1) extra memory.
• Predictable performance. The same number of comparisons every time, which simplifies performance analysis in constrained systems.

Disadvantages

• O(n²) in all cases with no adaptive behaviour, even on nearly sorted or already sorted input.
• Not stable. Long-distance swaps can disrupt the relative order of equal elements.
• Outperformed by insertion sort in almost every practical scenario involving small or nearly sorted arrays.
• Completely impractical for large datasets. Merge sort and quicksort are orders of magnitude faster.

Conclusion

Selection sort is the right tool for a narrow but real set of conditions: small arrays where minimising write operations matters more than minimising comparisons, and environments where predictable, input-independent performance is a constraint. For most other scenarios, insertion sort handles small data better and O(n log n) algorithms handle large data better. Understanding where selection sort fits, and where it does not, is exactly the depth of algorithmic reasoning that Interview Kickstart’s structured FAANG interview preparation program is built to develop.

FAQs: Selection Sort

Q1. What is the difference between selection sort and insertion sort?

Selection sort scans the full unsorted portion to find the minimum, then swaps it into place. It is not adaptive and always O(n²). Insertion sort takes the next element and shifts others to insert it correctly, it is adaptive and runs in O(n) on nearly sorted data.

Q2. Why is selection sort not used in practice for large datasets?

Its O(n²) time complexity in all cases means it gains nothing even on nearly sorted data. Merge sort and quicksort run in O(n log n) and are dramatically faster on large inputs.

Q3. Can selection sort be made stable?

Yes. Instead of swapping the minimum to the front, shift elements forward to create a gap and insert the minimum there. This preserves relative order but adds more write operations per pass.

Q4. How many swaps does selection sort make?

At most n-1 swaps for an array of n elements, one per pass, and only when the minimum is not already in its correct position. This is the lowest swap count of any simple sorting algorithm.

Q5. Is selection sort better than bubble sort?

Generally yes. Selection sort makes far fewer writes, which matters in write-sensitive environments. Both are O(n²) and impractical for large data, but selection sort’s swap efficiency gives it a consistent edge in those niche use cases.

References

1. Insertion Sort vs. Selection Sort

Recommended Reads:

• Comparison Among Selection Sort, Bubble Sort, and Insertion Sort
• Binary Insertion Sort
• Using Insertion Sort on a Singly Linked List
• Learn In-Place Merge Sort