selection sort

Complete

cs2040s
/
chapter2

cs
/
algorithms

lang
/
java

Summary

Selection sort

comparison based
iterative
in-place
not stable

Time complexity

all cases: - each pass sorts 1 element

Loop invariant

at the kth pass, the first k elements will be sorted into their final positions

Concept

Algorithm

start with the lower index at the first index
select the smallest value in the array, by comparison
swap it into the lowest index
increment the lowest index and repeat 2-3 to find the next smallest
repeat 2-3 until the lowest index is the last index

java

for (int i = 0; i < N-1; ++i) { // N-1 iterations
  cur_min = i;  
  for (int j = i+1; j < n; ++j)  
    if (A[j] < A[cur_min])
      cur_min = j;  
  swap(A, i, cur_min);  
}

“select” the current smallest