Category: Tech

This category is for technical posts

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

Insertion Sort

Imagine organizing a messy bookshelf, placing each book where it belongs one by one. That’s the essence of Insertion Sort, inserting each data element into its correct position like finding the perfect spot for your favourite novel.

Process

Imagine you have a messy pile of playing cards and want to sort them in your hand, one by one. That’s the essence of Insertion Sort! Here’s how it works:

1. Start with one card: Consider the first element in your data as the sorted “hand.” It’s already in its rightful place.

2. Draw a new card: Look at the next element in the unsorted data (like drawing a new card).

3. Find the right spot: Compare the new card to each card in your sorted hand, starting from the “back” (highest/lowest depending on sorting order).

4. Make space: If you find a card bigger (or smaller) than the new one, shift all cards after it one position to the right (or left) to create a gap.

5. Insert the new card: Slide the new card into the empty space you just created, ensuring it’s now in its correct order within the sorted hand.

6. Repeat: Keep drawing new cards, comparing, shifting,

Pseudo Code

Code
function insertionSort(array):
  for i in range(1, len(array)):
    key = array[i]
    j = i - 1
    while j >= 0 and array[j] > key:
      array[j + 1] = array[j]  # Shift elements to create space
      j -= 1
    array[j + 1] = key  # Insert key in its correct position
  return array
Explanation
  1. The insertionSort function takes an array as input.
  2. A for loop iterates through the array, starting from the second element (index 1), assuming the first element is already sorted.
  3. Inside the loop, the current element (key) is stored for comparison and potential insertion.
  4. Another while loop iterates backwards from the element before the key (j = i - 1), comparing elements with the key.
  5. If an element encountered in the inner loop is greater than the key, it’s shifted one position to the right to create space for the key.
  6. The inner loop continues shifting elements until a smaller element is found or the beginning of the array is reached.
  7. After the inner loop, the key is inserted into its correct position, ensuring sorted order up to that point.
  8. After all iterations, the array is sorted.

Implementations

Kotlin

Golang

Bubble Sort

Imagine sorting a messy pile of clothes, one swap at a time. That’s Bubble Sort in a nutshell! This simple algorithm might not be the speed king, but it’s a great way to understand sorting basics.

Process

Imagine you have a messy pile of toys and want to organize them by size. Bubble Sort does this by repeatedly comparing neighbouring toys:

  1. Start at the beginning: Compare the first two toys. If the second is bigger, swap their positions. This “bubbles” the larger toy towards the right.
  2. Repeat the comparison: Move one position to the right and compare the new pair. Swap if needed, again pushing the larger element further right.
  3. Keep going: Continue comparing and swapping pairs until you reach the end of the list. This completes one “pass.”
  4. Did we miss anything?: Repeat steps 1-3 from the beginning. With each pass, the largest element “bubbles” further right, leaving smaller ones sorted on the left.
  5. Are we done yet?: After a pass where no swaps occur, it means the list is sorted! You can celebrate with neatly organized toys (or data)!

Pseudo Code

Code
function bubbleSort(array):
  swapped = True
  while swapped:
    swapped = False
    for i in range(len(array) - 1):
      if array[i] > array[i + 1]:
        swap(array[i], array[i + 1])
        swapped = True
  return array

function swap(a, b):
  temp = a
  a = b
  b = temp
Explanation of code
  1. The bubbleSort function takes an array as input.
  2. A swapped flag is initialized to True. This flag will be used to track if any swaps occurred during a pass.
  3. A while loop continues as long as swapped is True. This means at least one swap occurred in the previous pass, and the list might not be fully sorted.
  4. Inside the loop, swapped is set to False at the beginning of each pass, assuming no swaps will occur.
  5. Another for loop iterates through the array (except the last element, as it’s already in its final position).
  6. If the current element is greater than the next element, they are swapped using the swap function. This “bubbles” the larger element towards the end of the list.
  7. If a swap occurs, the swapped flag is set to True to indicate that the list is not yet fully sorted.
  8. The swap function takes two elements and exchanges their values.
  9. After all passes, the loop terminates when swapped remains False, indicating the list is sorted.

Implementations

Kotlin

Golang