Step 2 of 7

29% Complete

Selection Sort

Learn the simple and intuitive Selection Sort algorithm

What is Selection Sort?

Selection Sort is a simple sorting algorithm that divides the array into two parts: sorted and unsorted. It repeatedly finds the minimum element from the unsorted part and moves it to the sorted part. Though easy to understand, it has O(n²) time complexity.

Selection Sort is less efficient than advanced algorithms but useful for small datasets and when memory writes need to be minimized.

How Selection Sort Works

Algorithm Steps

Find the minimum element in the unsorted portion
Swap it with the first element of the unsorted portion
Move the boundary between sorted and unsorted portions one element to the right
Repeat until entire array is sorted

Selection Sort - Visual Example

// Initial array: [64, 34, 25, 12, 22, 11, 90]
// Sorted part: []  |  Unsorted part: [64, 34, 25, 12, 22, 11, 90]
 
// Pass 1: Find min (11), swap with 64
// Sorted: [11]  |  Unsorted: [64, 34, 25, 12, 22, 90]
 
// Pass 2: Find min (12), swap with 64
// Sorted: [11, 12]  |  Unsorted: [64, 34, 25, 22, 90]
 
// Pass 3: Find min (22), swap with 64
// Sorted: [11, 12, 22]  |  Unsorted: [64, 34, 25, 90]
 
// Continue until sorted: [11, 12, 22, 25, 34, 64, 90]

Implementation

Selection Sort Implementation

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        
        // One by one move boundary of unsorted subarray
        for (int i = 0; i < n - 1; i++) {
            // Find minimum element in remaining unsorted array
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            
            // Swap the found minimum element with first element
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
    
    public static void main(String[] args) {
        int[] numbers = {64, 34, 25, 12, 22, 11, 90};
        selectionSort(numbers);
        System.out.println(Arrays.toString(numbers));
        // Output: [11, 12, 22, 25, 34, 64, 90]
    }
}

Time & Space Complexity

Time Complexity

Best: O(n²)

Average: O(n²)

Worst: O(n²)

Space Complexity

O(1) - In-place sorting

No extra data structures needed

Why O(n²)?

For each of n elements, we scan the remaining unsorted portion to find the minimum. This results in n + (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²) comparisons. Unlike Bubble Sort, the number of swaps is minimized to O(n).

Characteristics

✗ Not stable: May change order of equal elements

✓ In-place: Requires O(1) extra space

✗ Not adaptive: Always O(n²)

✓ Minimal writes: Only n-1 swaps max

When to Use Selection Sort

Good for:

Small datasets (n < 100)
When memory writes need to be minimized
Educational purposes
Situations requiring minimal data movement

Avoid for:

Large datasets
When stability is required
Performance-critical applications

Comparison with Other O(n²) Sorts

Aspect	Selection Sort	Bubble Sort	Insertion Sort
Time	O(n²)	O(n²)	O(n) to O(n²)
Swaps	O(n)	O(n²)	O(n²)
Stable	No	Yes	Yes
Adaptive	No	Yes	Yes

Key Takeaways

Selection Sort finds and places the minimum element each iteration
O(n²) time complexity with minimal memory writes (O(n) swaps)
In-place sorting, good for memory-constrained systems
Not stable, so equal elements may be reordered
Better than Bubble Sort due to fewer swaps
Useful for educational purposes and small datasets