Selection Sort Algorithm

Selection Sort repeatedly finds the smallest element in the unsorted portion and moves it to the front.

What is Selection Sort?

Selection Sort is a comparison-based sorting algorithm that repeatedly selects the smallest element from the unsorted part of the array and swaps it with the first element of that unsorted part.

The array is divided into two regions: a sorted region on the left and an unsorted region on the right. At every step, Selection Sort grows the sorted region by finding the minimum element from the unsorted region and placing it at the current position.

Core Intuition

Imagine you want to arrange numbers from smallest to largest. The simplest strategy is to first find the smallest number and place it at the beginning. Then find the next smallest number and place it in the second position. Continue this process until the entire array is sorted.

That is exactly what Selection Sort does. It does not try to fix neighboring pairs like Bubble Sort, and it does not shift elements like Insertion Sort. Instead, it repeatedly scans the remaining unsorted elements to select the minimum.

Selection Sort Algorithm Steps

1. Start from index 0.
   This index marks the beginning of the unsorted portion.
2. Assume the current index has the minimum value.
   Store its position as min_idx.
3. Scan the remaining unsorted elements.
   Compare every later element with the current minimum.
4. Update the minimum index.
   If a smaller element is found, update min_idx.
5. Swap the minimum into place.
   Swap the element at min_idx with the element at the current index.
6. Move to the next index.
   The sorted portion grows by one element after every pass.

Interactive Selection Sort Visualization

Use the visualization below to see how Selection Sort scans the unsorted portion, tracks the smallest value, and swaps it into the correct position.

Dry Run Example

Suppose we want to sort:

[64, 25, 12, 22, 11]

Pass 1: Find the smallest element

• Start at index 0. Current value is 64.
• Scan the rest of the array: 25, 12, 22, 11.
• The smallest value is 11.
• Swap 11 with 64 → [11, 25, 12, 22, 64]

Pass 2: Find the next smallest element

• The sorted portion is [11].
• Scan the unsorted portion: 25, 12, 22, 64.
• The smallest value is 12.
• Swap 12 with 25 → [11, 12, 25, 22, 64]

Pass 3: Find the next smallest element

• The sorted portion is [11, 12].
• Scan the unsorted portion: 25, 22, 64.
• The smallest value is 22.
• Swap 22 with 25 → [11, 12, 22, 25, 64]

Pass 4

• The remaining unsorted portion is [25, 64].
• 25 is already the smallest value in this portion.
• The array remains → [11, 12, 22, 25, 64]

The array is now sorted.

Selection Sort Code in Python

This implementation sorts the array in place. For each index, it finds the smallest element in the remaining unsorted portion and swaps it into the current position.

def selection_sort(arr):
    n = len(arr)

    for i in range(n - 1):
        min_idx = i

        # Find the index of the smallest element in the unsorted portion.
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j

        # Move the smallest element to its correct position.
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

    return arr


print(selection_sort([64, 25, 12, 22, 11]))

Time and Space Complexity

When Should You Use Selection Sort?

Interview Notes and Common Pitfalls

This section highlights the key concepts interviewers expect you to understand, along with common mistakes that can lead to incorrect implementations.

What interviewers may expect you to know

• Selection Sort repeatedly selects the minimum element from the unsorted portion.
• The sorted portion grows from left to right.
• It performs O(n²) comparisons in best, average, and worst cases.
• It is in-place because it uses O(1) extra space.
• It is generally not stable because swapping can change the relative order of equal elements.
• It performs fewer swaps than Bubble Sort in many cases.

Common mistakes

• Forgetting to reset min_idx to i at the start of each pass.
• Starting the inner loop from the wrong index.
• Swapping inside the inner loop instead of after finding the final minimum.
• Claiming Selection Sort has O(n) best-case time complexity.
• Calling it stable without explaining that standard Selection Sort is not stable.

Related coding interview problems

• Sort an Array
• Kth Largest Element in an Array
• Find K Pairs with Smallest Sums
• Top K Frequent Elements
• Sort Colors

Quick Quiz

Key Takeaways

• Selection Sort repeatedly finds the minimum element and places it at the front of the unsorted portion.
• After each pass, one more element is fixed in its final sorted position.
• It is simple and in place.
• It performs O(n²) comparisons in all cases.
• It makes at most O(n) swaps, which is its main advantage.
• It is usually not the best choice for optimized interview solutions.