Bubblesort

Bubble Sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted. Although easy to implement, its worst-case and average-case time complexity of \(O(n^2)\) makes it inefficient on large datasets.

Source Code Listing

code.ts

/*!
 * @file Bubblesort
 * @author Dustin Boston
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 *   Introduction to Algorithms. (2nd ed). The MIT Press.
 */

/**
 * Sorts an array using the bubble sort algorithm.
 *
 * @param array The array to be sorted.
 */
export function bubbleSort(array: number[]): void {
  for (let sortedIndex = 0; sortedIndex < array.length; sortedIndex++) {
    for (
      let currentIndex = array.length - 1;
      currentIndex > sortedIndex;
      currentIndex--
    ) {
      if (array[currentIndex] < array[currentIndex - 1]) {
        const swap = array[currentIndex];
        array[currentIndex] = array[currentIndex - 1];
        array[currentIndex - 1] = swap;
      }
    }
  }
}

test.ts

import {describe, expect, test} from "bun:test";
import {bubbleSort} from "./code.ts";

describe("Bubblesort", () => {
  test("Sort", () => {
    const a = [5, 2, 4, 6, 1, 3];
    bubbleSort(a);
    expect(a.toString()).toBe("1,2,3,4,5,6");
  });
});