sreejithmvarma.in

PCCST303 · Module 4: Sorting and Searching

Selection Sort

Sorting means arranging data into a chosen order, ascending or descending, so that later operations, especially searching, become faster and simpler. Selection sort is the most direct way to think about sorting: repeatedly find the smallest remaining value and put it where it belongs.

Idea

Definition

Selection sort divides the array into a sorted part (at the front, initially empty) and an unsorted part (the rest). On each pass, it finds the minimum value in the unsorted part and swaps it into the first position of the unsorted part, growing the sorted part by one.

Algorithm

SELECTION_SORT(A, N)
// A is the array to sort
// N is the number of elements in A
 
1. For i = 0 to N-2:
       MIN_INDEX = i
       For j = i+1 to N-1:
           If A[j] < A[MIN_INDEX]:
               MIN_INDEX = j
       Swap A[i] and A[MIN_INDEX]
2. Stop.

Worked example

Sorting [29, 10, 14, 37, 14] in ascending order:

Index
29
10
14
37
14
01234

Pass 1 (i = 0). Scan indices 1..4 for the minimum. Start with MIN_INDEX = 0 (29):

Index
29
10
14
37
14
01234
↑MIN

Since A[1] = 10 < 29, update MIN_INDEX = 1:

Index
29
10
14
37
14
01234
↑MIN

A[2] = 14, A[3] = 37, A[4] = 14: none beat 10. MIN_INDEX stays 1. Swap A[0] and A[1]:

Index
10
29
14
37
14
01234

Pass 2 (i = 1). Scan indices 2..4. MIN_INDEX = 1 (29) initially; A[2] = 14 < 29 updates it to 2; A[3] = 37 and A[4] = 14 don't beat 14. Swap A[1] and A[2]:

Index
10
14
29
37
14
01234

Pass 3 (i = 2). Scan indices 3..4. MIN_INDEX = 2 (29) initially; A[3] = 37 doesn't beat it; A[4] = 14 < 29 updates MIN_INDEX = 4. Swap A[2] and A[4]:

Index
10
14
14
37
29
01234

Pass 4 (i = 3). Scan index 4 only. Since A[4] = 29 < 37, update MIN_INDEX = 4. Swap A[3] and A[4]:

Index
10
14
14
29
37
01234

Sorted. With only one element left (N-1 positions placed), the last position is automatically correct, no pass needed for i = N-1.

Complexity

Key Idea

Selection sort always scans the entire remaining unsorted part on every pass, regardless of how close to sorted the array already is. This makes its comparison count fixed, (N-1) + (N-2) + ... + 1 = N(N-1)/2, the same in the best, average, and worst case.

MeasureComplexity
Comparisons (best, average, worst)O(N²)
SwapsO(N)
SpaceO(1)
StabilityNot stable

Selection sort is not stable, since a swap can move a value past another equal value, changing their original relative order.

Selection sort's number of swaps is much lower than most O(N²) sorts, at most N-1 total, since it swaps only once per pass. This makes it attractive when writing (not comparing) is the expensive operation, e.g. sorting data on flash memory where writes wear out cells.

Quick recall

  • Grows a sorted prefix by repeatedly finding the minimum of the unsorted suffix and swapping it into place.
  • O(N²) comparisons always, regardless of input order; at most O(N) swaps.
  • In-place (O(1) extra space); not stable.
  • Fewer swaps than most simple sorts, useful when writes are expensive.