Bubble Sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. This process is repeated until the entire array is sorted. Named for the way larger elements 'bubble' to the top (end) of the array.
Visualization
Interactive visualization for Bubble Sort
Animation Speed: 300ms
🔵 Blue: Comparing | 🟢 Green: Sorted
Interactive visualization with step-by-step execution
Implementation
1function bubbleSort(arr: number[]): number[] {
2 const n = arr.length;
3 const sorted = [...arr];
4 let swapped: boolean;
5
6 // Optimized version with early termination
7 for (let i = 0; i < n - 1; i++) {
8 swapped = false;
9
10 // Last i elements are already in place
11 for (let j = 0; j < n - i - 1; j++) {
12 if (sorted[j] > sorted[j + 1]) {
13 // Swap adjacent elements
14 [sorted[j], sorted[j + 1]] = [sorted[j + 1], sorted[j]];
15 swapped = true;
16 }
17 }
18
19 // If no swaps occurred, array is sorted
20 if (!swapped) break;
21 }
22 return sorted;
23}
24
25// Example usage:
26const arr = [64, 34, 25, 12, 22, 11, 90];
27console.log(bubbleSort(arr)); // [11, 12, 22, 25, 34, 64, 90]Deep Dive
Theoretical Foundation
Bubble Sort is a comparison-based sorting algorithm that works by repeatedly stepping through the list, comparing adjacent pairs of elements and swapping them if they are in the wrong order. The algorithm gets its name because smaller elements 'bubble' to the top of the list (beginning) while larger elements sink to the bottom (end). Despite its simplicity and ease of understanding, Bubble Sort is rarely used in practice due to its poor performance on large datasets. However, it can be optimized with a flag to detect if any swaps were made in a pass - if no swaps occur, the array is already sorted and the algorithm can terminate early.
Complexity
Time
O(n) - when array is already sorted with optimization
O(n²) - typical case with random data
O(n²) - when array is reverse sorted
Space
O(1) - only uses a constant amount of additional space
Applications
Industry Use
Introduction to sorting algorithms in computer science education
Polygon filling algorithms in computer graphics
Sorting small embedded system data where code simplicity matters
Use Cases
Related Algorithms
Quicksort
A highly efficient, in-place sorting algorithm that uses divide-and-conquer strategy. Invented by Tony Hoare in 1959, it remains one of the most widely used sorting algorithms due to its excellent average-case performance and cache efficiency.
Merge Sort
A stable, divide-and-conquer sorting algorithm with guaranteed O(n log n) performance.
Insertion Sort
Insertion Sort is a simple, intuitive sorting algorithm that builds the final sorted array one element at a time. It works similarly to how people sort playing cards in their hands - picking each card and inserting it into its correct position among the already sorted cards. Despite its O(n²) time complexity, Insertion Sort is efficient for small datasets and nearly sorted arrays, making it practical for real-world applications.
Selection Sort
Selection Sort is a simple comparison-based sorting algorithm that divides the array into sorted and unsorted regions. It repeatedly selects the smallest (or largest) element from the unsorted region and moves it to the end of the sorted region. The algorithm performs the minimum number of swaps (n-1 at most), making it useful when memory writes are expensive operations.