Yep, you heard me right the most boring topic ever to grace this earth.
First: what is sorting anyway? Well, let’s say you have a list of numbers or words that are all jumbled up. You want to put them in order from smallest to largest (or alphabetically). That’s where sorting comes in! It takes your unsorted mess and turns it into something resembling a neatly organized library shelf.
Now, some of the most popular sorting algorithms out there: bubble sort, insertion sort, selection sort, quicksort, mergesort, heapsort…the list goes on and on. But for our purposes today, we’re going to focus on three of them that are relatively simple to understand (and implement) bubble sort, insertion sort, and selection sort.
Bubble Sort: This algorithm is like a game of “hot potato” with your numbers or words. You start by comparing the first two elements in your list, swapping them if they’re out of order. Then you move on to the next pair (the second and third elements), compare them, swap if necessary…and so on until you reach the end of the list. At that point, you repeat this process for each subsequent pair of adjacent elements hence the name “bubble sort”.
Here’s what it looks like in Python:
# Define a function named bubble_sort that takes in an array as its argument
def bubble_sort(arr):
# Get the length of the array
n = len(arr)
# Loop through all array elements except the last one
for i in range(n-1):
# Loop through remaining unsorted elements from right to left
for j in range(0, n-i-1):
# Compare the current element with the next element
if arr[j] > arr[j+1]:
# Swap the two elements if they're out of order
arr[j], arr[j+1] = arr[j+1], arr[j]
# Return the sorted array
return arr
Insertion Sort: This algorithm is like a game of “Simon Says” with your numbers or words. You start by comparing the first element in your list to every subsequent element, inserting it into its correct position if necessary (like Simon says). Then you move on to the second element and repeat the process compare it to all elements after it, inserting it into its correct position if needed…and so on until you reach the end of the list.
Here’s what it looks like in Python:
# This function implements the insertion sort algorithm to sort a given array in ascending order
def insertion_sort(arr):
# Get the length of the array
n = len(arr)
# Loop through all array elements except the first one (since we don't need to compare the first element with anything)
for i in range(1, n):
# Set the current element as the key to be compared with other elements
key = arr[i]
# Set the index of the element before the current element
j = i - 1
# Move elements of arr[0..j], that are greater than key, to one position ahead of their current position
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j] # Shift the element to the right
j -= 1 # Decrement j to compare with the previous element
# Insert the key into its correct position in arr[0..j]
arr[j+1] = key
# Return the sorted array
return arr
Selection Sort: This algorithm is like a game of “Choose Your Own Adventure” with your numbers or words. You start by finding the smallest (or largest) element in your list, and then swapping it with the first (or last) unsorted element. Then you move on to find the next smallest (or largest) element, and repeat this process until all elements are sorted.
Here’s what it looks like in Python:
# Define a function named selection_sort that takes in a list as its argument
def selection_sort(arr):
# Find the length of the list and assign it to variable n
n = len(arr)
# Loop through the unsorted list, starting from the first element
for i in range(n-1):
# Assign the current index to variable min_idx
min_idx = i
# Loop through the remaining unsorted elements, starting from the next index
for j in range(i+1, n):
# Compare the current element with the element at min_idx
if arr[j] < arr[min_idx]:
# If the current element is smaller, update min_idx to the current index
min_idx = j
# Swap the smallest element with the first unsorted element
arr[i], arr[min_idx] = arr[min_idx], arr[i]
# Return the sorted list
return arr
And there you have it three simple sorting algorithms that will make your computer cry. But hey, at least they’re not as boring as the topic itself!