Basic Sorting Algorithms

Sorting is the process of arranging data in a specific order (usually ascending or descending). While modern languages have built-in highly optimized sorting functions (like Array.prototype.sort()), understanding basic sorting algorithms is crucial for fundamental algorithmic thinking.

These three basic algorithms all share a terrible worst-case time complexity of $O(N^2)$, making them unsuitable for large datasets.

1. Bubble Sort

The simplest sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The largest elements "bubble up" to the end of the list first.

• Time Complexity: $O(N^2)$ (Average & Worst), $O(N)$ (Best case - already sorted)
• Space Complexity: $O(1)$ (In-place)

function bubbleSort(arr: number[]): number[] {
  let swapped = false;
  
  for (let i = 0; i < arr.length; i++) {
    swapped = false;
    // The last 'i' elements are already sorted, no need to check them
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // Swap adjacent elements
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = true;
      }
    }
    // Optimization: If no elements were swapped, the array is sorted!
    if (!swapped) break;
  }
  return arr;
}

2. Selection Sort

This algorithm divides the input into two parts: a sorted subarray and an unsorted subarray. It repeatedly finds the minimum element from the unsorted part and swaps it with the first element of the unsorted part.

• Time Complexity: $O(N^2)$ (Always)
• Space Complexity: $O(1)$ (In-place)

function selectionSort(arr: number[]): number[] {
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i;
    
    // Find the minimum element in the remaining unsorted array
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    
    // Swap the found minimum element with the first unsorted element
    if (minIndex !== i) {
      const temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
  return arr;
}

3. Insertion Sort

Insertion sort builds the final sorted array one item at a time. It takes an element from the unsorted part and "inserts" it into its correct mathematical position in the sorted part by shifting larger elements to the right. Analogy: This is exactly how most humans sort playing cards in their hands.

• Time Complexity: $O(N^2)$ (Worst case), $O(N)$ (Best case - almost sorted)
• Space Complexity: $O(1)$ (In-place)

[!TIP] While $O(N^2)$ generally, Insertion Sort is incredibly fast (approaching $O(N)$) on arrays that are already mostly sorted or very small. In fact, advanced algorithms like V8's Timsort use Insertion Sort for small subarrays!

function insertionSort(arr: number[]): number[] {
  for (let i = 1; i < arr.length; i++) {
    const currentVal = arr[i];
    let j = i - 1;
    
    // Shift elements of the sorted segment to the right 
    // to create the gap for currentVal
    while (j >= 0 && arr[j] > currentVal) {
      arr[j + 1] = arr[j];
      j--;
    }
    
    // Insert the element into the gap
    arr[j + 1] = currentVal;
  }
  return arr;
}