Selection Sort

Selection sort is a simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted portion and placing it at the beginning. It divides the array into a sorted portion (initially empty) and an unsorted portion (initially the entire array).

Play

Properties

• Comparison-based: Works by comparing elements to find minimum
• In-place sorting: Sorts the array without using extra space
• Unstable algorithm: Does not maintain relative order of equal elements
• Simple implementation: Easy to understand and implement

How it Works

1. Start with first position: Assume first element is the minimum
2. Find minimum in unsorted portion: Scan through unsorted part to find the actual minimum
3. Swap with first position: Replace the first element with the found minimum
4. Move to next position: The first element is now sorted, move to second position
5. Repeat: Find minimum in remaining unsorted portion and swap with current position
6. Continue: Repeat until all elements are in their correct positions
7. Done: Array is fully sorted when all positions are filled

Use Cases

• Educational purposes: Good for learning sorting concepts
• Small datasets: Acceptable for very small arrays
• Memory-constrained environments: Uses minimal extra memory
• When simplicity matters: When implementation simplicity is priority

Time Complexity

• Best case: O(n²) - Even when array is already sorted
• Average case: O(n²) - Random order of elements
• Worst case: O(n²) - When array is reverse sorted

Note: Unlike bubble sort, selection sort always performs O(n²) comparisons regardless of input.

Space Complexity

• O(1): Constant space, only uses a few variables

Advantages

• Simple to understand: Intuitive algorithm concept
• In-place sorting: Minimal memory requirements
• Consistent performance: Always O(n²), predictable behavior
• Minimum number of swaps: Makes at most n-1 swaps

Disadvantages

• Poor performance: O(n²) time complexity for all cases
• Not adaptive: Doesn’t improve performance for partially sorted arrays
• Unstable: May change relative order of equal elements
• Not suitable for large datasets: Inefficient for large arrays

Example

public class SelectionSort {
  // Selection sort implementation
  public static void selectionSort(int[] array) {

    // 📌 Part 1: Traverse through all array elements
    for (int i = 0; i < array.length - 1; i++) {

      // 📌 Part 2: Find the minimum element in remaining unsorted array
      int minIndex = i;

      // 📌 Part 3: Scan through unsorted portion
      for (int j = i + 1; j < array.length; j++) {

        // 📌 Part 4: Update minIndex if current element is smaller
        if (array[j] < array[minIndex]) {
          minIndex = j;
        }

      }

      // 📌 Part 5: Swap the found minimum element with the first element
      if (minIndex != i) {
        int temp = array[minIndex];
        array[minIndex] = array[i];
        array[i] = temp;
      }

    }

  }

  public static void main(String[] args) {
    int[] numbers = {64, 34, 25, 12, 22, 11, 90};

    System.out.print("Original: ");
    for (int num : numbers) {
      System.out.print(num + " ");
    }

    selectionSort(numbers);
    System.out.println();

    System.out.print("Sorted: ");
    for (int num : numbers) {
      System.out.print(num + " ");
    }
  }
}

Visualization