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