Introduction

Selection Sort is a simple comparison-based sorting algorithm.

The idea is:

  • repeatedly find the minimum element
    from the unsorted portion
  • place it at the correct position

After every pass:

  • one element gets fixed permanently

This problem helps in understanding:

  • sorting fundamentals
  • minimum element selection
  • swapping logic
  • in-place sorting

Example

Input:arr = [64, 25, 12, 22, 11]

Output:
[11, 12, 22, 25, 64]

Explanation:
Smallest element is selected and moved to correct position during every pass.
Constraints
 1 <= arr.length <= 10^5-10^4 <= arr[i] <= 10^4

Approach 1 : Basic Selection Sort

Explanation

The simplest way to sort using Selection Sort is:

  1. Find smallest element
    from unsorted portion
  2. Swap it with current index
  3. Repeat for remaining elements

After every pass:

  • left portion becomes sorted

Steps

  1. Traverse array.
  2. Find minimum element.
  3. Swap with current position.
  4. Continue remaining passes.
  5. Return sorted array.

Dry Run

Input:[64, 25, 12, 22, 11]
Pass 1:
Minimum element:
11
Swap with 64

Array becomes:
[11, 25, 12, 22, 64]

Pass 2:
Minimum element:
12
Swap with 25

Array becomes:
[11, 12, 25, 22, 64]

Continue remaining passes...

Final Result:
[11, 12, 22, 25, 64]

Basic Selection Sort Code

Complexity Analysis

Time Complexity: O(n²)Explanation:Minimum element is searched during every pass.

Space Complexity: O(1)
Explanation:
Sorting is performed in-place.

Approach 2 : Optimized Selection Sort

Explanation

Selection Sort already performs:

  • minimum possible swaps

Optimization idea:

  • avoid unnecessary swapping
    when minimum element
    is already at correct position

This reduces redundant operations.

Steps

  1. Traverse array.
  2. Find minimum element.
  3. Check if swap is needed.
  4. Swap only if required.
  5. Return sorted array.

Dry Run

Input:[11, 12, 22, 25]

Pass 1:
Minimum element already:
11
No swap needed

Pass 2:
Minimum element already:
12
No swap needed
Array already sorted

Final Result:
[11, 12, 22, 25]

Optimized Selection Sort Code

Complexity Analysis

Best Case Time Complexity: O(n²)
Average Case Time Complexity: O(n²)

Worst Case Time Complexity: O(n²)

Explanation:
Minimum searching is always required.

Space Complexity: O(1)

Explanation:
Sorting is performed in-place.

Edge Cases

  1. Empty array
  2. Single element array
  3. Already sorted array
  4. Reverse sorted array
  5. Duplicate elements present

Why This Problem is Important

Selection Sort helps in understanding:

  1. Sorting fundamentals
  2. Minimum element selection
  3. Swapping logic
  4. In-place sorting
  5. Comparison-based sorting

It is one of the most important beginner sorting algorithms.

Real-World Applications

Selection Sort concepts are used in:

  1. Educational visualization
  2. Small datasets
  3. Memory-constrained systems
  4. Algorithm teaching tools
  5. Embedded systems

Common Mistakes

  1. Incorrect minimum index update
  2. Wrong swap logic
  3. Incorrect loop bounds
  4. Forgetting minimum initialization

Interview Tips

Interviewers often expect:

  1. Sorting fundamentals
  2. Minimum selection understanding
  3. Time complexity explanation

Always explain why:

  • one element gets fixed
    after every pass

Related Questions

  1. Bubble Sort
  2. Insertion Sort
  3. Merge Sort
  4. Quick Sort
  5. Sort Colors

Final Takeaway

Selection Sort is a fundamental comparison-based sorting algorithm that teaches minimum element selection and in-place sorting techniques. Understanding Selection Sort builds a strong foundation for advanced sorting algorithms and interview problems.