Basic Sorts (Bubble, Selection, Insertion)

Basic Sorting Algorithms

Welcome to the world of sorting! These fundamental algorithms—Bubble Sort, Selection Sort, and Insertion Sort—are the building blocks for understanding more complex sorting methods. While not the most efficient, they provide a clear introduction to the logic of ordering data.

---

1. Bubble Sort

Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

• The Core Idea: Larger elements "bubble" up to the end of the list with each pass.

• Implementation:

  function bubbleSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
      for (let j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          // Swap adjacent elements
          [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        }
      }
    }
    return arr;
  }
  

• Complexity:

  • Time: O(N^2) in all cases.
  • Space: O(1).

---

2. Selection Sort

Selection Sort divides the list into two parts: a sorted sublist and an unsorted sublist. It repeatedly finds the minimum element from the unsorted sublist and moves it to the end of the sorted sublist.

• The Core Idea: In each iteration, select the smallest remaining element and place it in its correct position.

• Implementation:

  function selectionSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
      let minIndex = i;
      for (let j = i + 1; j < n; j++) {
        if (arr[j] < arr[minIndex]) {
          minIndex = j;
        }
      }
      // Swap the found minimum element with the first element
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
    return arr;
  }
  

• Complexity:

  • Time: O(N^2) in all cases.
  • Space: O(1).

---

3. Insertion Sort

Insertion Sort also builds the final sorted array one item at a time. It iterates through the input elements and, for each element, it finds the correct position in the sorted part of the array and inserts it there.

• The Core Idea: Like sorting a hand of playing cards. You take one card at a time and insert it into its correct place among the cards you're already holding.

• Implementation:

  function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
      let current = arr[i];
      let j = i - 1;
      // Move elements of arr[0..i-1], that are greater than current,
      // to one position ahead of their current position
      while (j >= 0 && arr[j] > current) {
        arr[j + 1] = arr[j];
        j--;
      }
      arr[j + 1] = current;
    }
    return arr;
  }
  

• Complexity:

  • Time: O(N^2) in the worst case, but O(N) in the best case (for nearly sorted data).
  • Space: O(1).

---

Key Takeaway: Basic sorts like Bubble, Selection, and Insertion Sort are simple to understand and implement, but their O(N^2) time complexity makes them inefficient for large datasets. Insertion Sort is often the most practical of the three for small or nearly sorted inputs.