Selection Sort

Ever played “musical chairs” but with data elements? Selection Sort takes on this playful premise, ensuring each element finds its correct “chair” by repeatedly selecting the smallest and swapping it into place.

Process

Think of your data as a jumbled classroom. Selection Sort helps put everyone in their perfect seat, one by one. Here’s how:

  1. Pick a seat: Choose the first element as the “smallest” (or “largest”). It’s temporarily in its spot.
  2. Look around: Check everyone else (except the teacher’s pet in the front row, they’re already sorted!).
  3. Find the misplaced soul: If someone’s smaller (or larger) than the current “smallest,” remember their name! They’re the true contender.
  4. Switch desks: Swap the current “smallest” with the true contender. Now they’re both in the right place (sort of)!
  5. Repeat the process: Ignore the front row (sorted!), and start again from the next seat. Keep finding the truly smallest (or largest) and swapping them in.
  6. Class dismissed! Once everyone has switched seats the right number of times, the classroom (data) is perfectly sorted!

Pseudo Code

Code
function selectionSort(array):
  for i in range(len(array) - 1):
    min_index = i
    for j in range(i + 1, len(array)):
      if array[j] < array[min_index]:
        min_index = j
    swap(array[i], array[min_index])
  return array

function swap(a, b):
  temp = a
  a = b
  b = temp
Explanation
  1. The selectionSort function takes an array as input.
  2. A for loop iterates through the array (except the last element, as it’s already in its final position).
  3. Inside the loop, a min_index variable is initialized to the current index (i). This assumes the element at this index is the smallest (or largest) so far.
  4. Another for loop iterates from the next element (i + 1) to the end of the array.
  5. If an element encountered in the inner loop is smaller (or larger) than the current min_index element, its index is stored in min_index. This new element becomes the candidate for the smallest (or largest).
  6. After the inner loop, the element at min_index is swapped with the element at the current index (i) using the swap function. This effectively places the smallest (or largest) element found so far in its correct position.
  7. The swap function takes two elements and exchanges their values.
  8. After all passes, the loop terminates, leaving the array sorted.

Implementations

Kotlin

Golang