Insertion Sort 🎯

Welcome to the fascinating world of Data Structures and Algorithms! Today, we'll be diving into the depths of Insertion Sort, a fundamental sorting algorithm used to organize data in a way that can significantly improve the efficiency of your code.

What is Insertion Sort? 📝

Insertion Sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It works by inserting each element into its correct position in a sorted list, which we create during the sorting process.

How Does Insertion Sort Work? 💡

Imagine you're organizing a deck of cards. Instead of shuffling and then sorting them like a traditional sorting algorithm, you'd insert each new card into its correct position in a smaller, already sorted stack. That's exactly what Insertion Sort does!

Steps of Insertion Sort 📝

Start from the second element of the array (or list). This element is the first one to be sorted.
Compare the current element with the ones to its left.
If the current element is smaller, swap it with the previous element and continue comparing until you find the correct position or reach the beginning of the array.
Repeat the process for the next unsorted element.
The array is sorted once all elements have been processed.

Code Example 💻 (Python)

python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# Test the function
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print(arr)  # Output: [5, 6, 11, 12, 13]

Code Example 💻 (JavaScript)

javascript

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }

  // Test the function
  let arr = [12, 11, 13, 5, 6];
  insertionSort(arr);
  console.log(arr);  // Output: [5, 6, 11, 12, 13]
}

Quiz Time! 📝

Keep learning, and remember: practice makes perfect! Happy coding! 🚀