Selection Sort

Selection Sort is a simple comparison-based sorting algorithm that divides the array into a sorted part and an unsorted part. On every pass, it selects the smallest (or largest, depending on order) element from the unsorted part and swaps it into its correct position at the end of the sorted part.

Unlike Insertion Sort, which shifts many elements, Selection Sort makes at most one swap per pass but it always scans the entire unsorted portion to find the minimum.

How Selection Sort Works?

  1. Start with the first position (index 0) as the current position.
  2. Search the entire unsorted part of the array to find the smallest element.
  3. Swap this smallest element with the element at the current position.
  4. Move the boundary between sorted and unsorted parts one step to the right.
  5. Repeat until the whole array is sorted.

Example: Sorting [29, 10, 14, 37, 13]

Initial array: [29, 10, 14, 37, 13]

Pass 1 (i = 0):

  • Search index 0 to 4 for minimum → minimum is 10 (index 1)
  • Swap array[0] and array[1]
  • Array: [10, 29, 14, 37, 13]

Pass 2 (i = 1):

  • Search index 1 to 4 for minimum → minimum is 13 (index 4)
  • Swap array[1] and array[4]
  • Array: [10, 13, 14, 37, 29]

Pass 3 (i = 2):

  • Search index 2 to 4 for minimum → minimum is 14 (already at index 2)
  • No swap needed
  • Array: [10, 13, 14, 37, 29]

Pass 4 (i = 3):

  • Search index 3 to 4 for minimum → minimum is 29 (index 4)
  • Swap array[3] and array[4]
  • Array: [10, 13, 14, 29, 37]

Final Sorted Array: [10, 13, 14, 29, 37]

PassMinimum foundSwap performedResulting Array
110swap(0,1)[10, 29, 14, 37, 13]
213swap(1,4)[10, 13, 14, 37, 29]
314no swap[10, 13, 14, 37, 29]
429swap(3,4)[10, 13, 14, 29, 37]

Pseudocode

Step 1: Start
Step 2: For i = 0 to n-2, repeat steps 3 to 6
Step 3:     minIndex = i
Step 4:     For j = i+1 to n-1:
                If array[j] < array[minIndex]:
                    minIndex = j
Step 5:     Swap array[i] and array[minIndex]
Step 6: End loop
Step 7: End

Advantages

  • Simple to understand and implement.
  • Performs a minimal number of swaps at most (n-1) swaps total, which is useful when write/swap operations are costly (e.g., writing to flash memory).
  • Works in-place, requiring no extra storage.
  • Performance does not depend on the initial order of data (always makes the same number of comparisons).

Disadvantages

  • Always O(n²) comparisons, even if the array is already sorted — it is not adaptive.
  • Generally slower in practice than Insertion Sort for small or nearly-sorted datasets.
  • Not stable in its standard implementation (equal elements may change relative order), although a stable version can be written with extra effort.
  • Inefficient for large datasets compared to O(n log n) algorithms.

Time and Space Complexity

CaseTime ComplexityExplanation
Best CaseO(n²)Even a sorted array is fully scanned to confirm minimums
Average CaseO(n²)Random order data
Worst CaseO(n²)Reverse sorted data

Space Complexity: O(1) — sorting happens in-place using only a few extra variables.

Stability: Not stable (by default) In-place: Yes Number of swaps: At most n − 1 (a key strength of this algorithm)

When to Use Selection Sort?

  • When the cost of swapping/writing elements is high, and minimizing swaps matters more than minimizing comparisons.
  • For small datasets where simplicity is preferred over speed.
  • Educational purposes, to introduce the concept of sorting.

Practice Questions (Solve on your own)

  1. Sort the array [64, 25, 12, 22, 11] using Selection Sort, showing the array after every pass.
  2. How many total comparisons does Selection Sort make for an array of 6 elements? Derive the formula.
  3. For the array [5, 5, 3, 1], trace Selection Sort and check whether equal elements maintain their original order.
  4. Sort [1, 2, 3, 4, 5] (already sorted) using Selection Sort. How many swaps are actually performed?
  5. Modify the Selection Sort algorithm to sort the array in descending order and write its pseudocode.
  6. For the array [45, 12, 78, 3, 9], identify the minimum found and the swap made in each pass.
  7. Compare the total number of swaps in Selection Sort versus Insertion Sort for the array [9, 8, 7, 6, 5].
  8. Write a program to implement Selection Sort that also counts and prints the total number of comparisons and swaps.
  9. Explain, using an example array of 4 elements, why the standard Selection Sort algorithm is not stable.
  10. Given the array [33, 12, 45, 6, 21], sort it manually with Selection Sort and list the minimum element identified in each pass.
Previous Post
Insertion Sort
Next Post
Quick Sort
0 people found this article helpful

Was this article helpful?