Bubble Sort and Selection Sort

Overview

Bubble sort and selection sort are fundamental comparison-based sorting algorithms that organize elements in a collection by repeatedly comparing and swapping values. Both algorithms operate in-place, modifying the original array without requiring additional memory proportional to the input size.

Bubble sort works by repeatedly stepping through the array, comparing adjacent elements and swapping them if they are in the wrong order. Each complete pass through the array guarantees that the largest unsorted element moves to its final position, similar to how bubbles rise to the surface of water. The algorithm continues making passes until no swaps occur, indicating the array is sorted.

Selection sort divides the array into sorted and unsorted regions. The algorithm repeatedly finds the minimum element from the unsorted region and places it at the end of the sorted region. Unlike bubble sort, selection sort performs exactly n-1 passes through the array regardless of the initial ordering, where n is the number of elements.

Both algorithms serve as educational tools for understanding sorting mechanics, comparison operations, and algorithm analysis. While rarely used in production systems due to poor performance on large datasets, they demonstrate core concepts that appear in more advanced sorting algorithms. Bubble sort introduces the concept of optimization through early termination, while selection sort illustrates the divide-and-conquer principle of maintaining sorted and unsorted regions.

These algorithms appear in systems with severe memory constraints where the constant space complexity outweighs the quadratic time complexity, and in situations where the number of elements remains small enough that the performance difference between sorting algorithms becomes negligible.

Key Principles

Comparison-based sorting algorithms establish order by comparing pairs of elements and making decisions based on those comparisons. Both bubble sort and selection sort rely exclusively on comparison operations, never using element values directly for positioning decisions. This property makes them stable sorting algorithms when implemented correctly, preserving the relative order of equal elements.

The in-place property means both algorithms sort the array using only a constant amount of extra memory beyond the input array. They achieve this by swapping elements within the original array rather than creating copies. The space complexity of O(1) represents a significant advantage in memory-constrained environments.

Bubble sort operates through adjacent comparisons. During each pass, the algorithm compares consecutive elements at positions i and i+1. When elements are out of order, the algorithm swaps them. After each complete pass, the largest element in the unsorted portion moves to its final position. This behavior creates the characteristic bubbling effect where larger values progressively move toward the end of the array.

The algorithm maintains an optimization flag that tracks whether any swaps occurred during a pass. If a complete pass finishes without swaps, the array is sorted and the algorithm terminates early. This optimization provides best-case O(n) time complexity when the input is already sorted, though the worst-case and average-case scenarios remain O(n²).

Selection sort operates through minimum-finding operations. The algorithm divides the array into two regions: a sorted prefix and an unsorted suffix. Initially, the sorted region contains zero elements. During each iteration, the algorithm scans the entire unsorted region to find the minimum element, then swaps this minimum with the first element of the unsorted region. This operation expands the sorted region by one element.

The algorithm performs exactly n-1 iterations for an array of n elements. Each iteration finds one minimum value, requiring progressively fewer comparisons as the unsorted region shrinks. The total number of comparisons remains constant regardless of initial array ordering, resulting in O(n²) time complexity for all cases.

Stability differs between the two algorithms. Bubble sort maintains stability naturally because it only swaps adjacent elements when they are strictly out of order. Equal elements never swap positions relative to each other. Selection sort becomes unstable in its standard form because swapping the minimum element with the first unsorted element can move equal elements past each other. A stable version of selection sort requires additional complexity.

Both algorithms demonstrate the trade-off between comparison count and swap count. Bubble sort minimizes swaps by only exchanging adjacent elements, potentially requiring many swaps to move an element to its final position. Selection sort minimizes swaps by ensuring each swap places an element in its final position, performing at most n-1 swaps total. This difference matters when swap operations are expensive compared to comparisons, such as when sorting large objects or records.

Ruby Implementation

Ruby's built-in Array class provides sort and sort_by methods that use optimized sorting algorithms, typically Timsort or quicksort depending on the Ruby implementation. Implementing bubble sort and selection sort in Ruby demonstrates algorithm concepts and comparison operators.

Basic bubble sort implementation:

def bubble_sort(array)
  n = array.length
  
  (n - 1).times do
    (n - 1).times do |i|
      if array[i] > array[i + 1]
        array[i], array[i + 1] = array[i + 1], array[i]
      end
    end
  end
  
  array
end

numbers = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(numbers)
# => [11, 12, 22, 25, 34, 64, 90]

Optimized bubble sort with early termination:

def bubble_sort_optimized(array)
  n = array.length
  
  (n - 1).times do |pass|
    swapped = false
    
    (n - 1 - pass).times do |i|
      if array[i] > array[i + 1]
        array[i], array[i + 1] = array[i + 1], array[i]
        swapped = true
      end
    end
    
    break unless swapped
  end
  
  array
end

numbers = [5, 1, 4, 2, 8]
bubble_sort_optimized(numbers)
# => [1, 2, 4, 5, 8]

The optimized version includes two improvements. The swapped flag enables early termination when the array becomes sorted. The inner loop limit of n - 1 - pass reduces unnecessary comparisons by excluding elements already in their final positions.

Basic selection sort implementation:

def selection_sort(array)
  n = array.length
  
  (n - 1).times do |i|
    min_index = i
    
    (i + 1...n).each do |j|
      min_index = j if array[j] < array[min_index]
    end
    
    array[i], array[min_index] = array[min_index], array[i] if i != min_index
  end
  
  array
end

numbers = [64, 25, 12, 22, 11]
selection_sort(numbers)
# => [11, 12, 22, 25, 64]

Ruby implementation using blocks for custom comparison:

def bubble_sort_by(array, &block)
  n = array.length
  comparator = block || proc { |a, b| a <=> b }
  
  (n - 1).times do |pass|
    swapped = false
    
    (n - 1 - pass).times do |i|
      if comparator.call(array[i], array[i + 1]) > 0
        array[i], array[i + 1] = array[i + 1], array[i]
        swapped = true
      end
    end
    
    break unless swapped
  end
  
  array
end

words = ["zebra", "apple", "mango", "berry"]
bubble_sort_by(words) { |a, b| a.length <=> b.length }
# => ["apple", "zebra", "mango", "berry"]

Selection sort with custom comparison:

def selection_sort_by(array)
  n = array.length
  
  (n - 1).times do |i|
    min_index = i
    
    (i + 1...n).each do |j|
      min_index = j if yield(array[j], array[min_index]) < 0
    end
    
    array[i], array[min_index] = array[min_index], array[i] if i != min_index
  end
  
  array
end

people = [
  { name: "Alice", age: 30 },
  { name: "Bob", age: 25 },
  { name: "Charlie", age: 35 }
]

selection_sort_by(people) { |a, b| a[:age] <=> b[:age] }
# => [{ name: "Bob", age: 25 }, { name: "Alice", age: 30 }, { name: "Charlie", age: 35 }]

Descending order implementation:

def bubble_sort_descending(array)
  n = array.length
  
  (n - 1).times do |pass|
    swapped = false
    
    (n - 1 - pass).times do |i|
      if array[i] < array[i + 1]  # Reversed comparison
        array[i], array[i + 1] = array[i + 1], array[i]
        swapped = true
      end
    end
    
    break unless swapped
  end
  
  array
end

numbers = [3, 7, 1, 9, 4]
bubble_sort_descending(numbers)
# => [9, 7, 4, 3, 1]

Ruby idiomatic approach using Enumerable methods:

class Array
  def bubble_sort!
    n = length
    
    (n - 1).times do |pass|
      swapped = false
      
      (n - 1 - pass).times do |i|
        if self[i] > self[i + 1]
          self[i], self[i + 1] = self[i + 1], self[i]
          swapped = true
        end
      end
      
      break unless swapped
    end
    
    self
  end
  
  def selection_sort!
    n = length
    
    (n - 1).times do |i|
      min_index = ((i + 1)...n).min_by { |j| self[j] } || i
      min_index = i if self[i] <= self[min_index]
      
      self[i], self[min_index] = self[min_index], self[i] if i != min_index
    end
    
    self
  end
end

[5, 2, 8, 1, 9].bubble_sort!
# => [1, 2, 5, 8, 9]

Practical Examples

Sorting a small array of integers demonstrates basic algorithm behavior:

def demonstrate_bubble_sort
  array = [5, 2, 8, 1, 9]
  puts "Original: #{array}"
  
  n = array.length
  pass = 0
  
  (n - 1).times do
    swapped = false
    puts "\nPass #{pass + 1}:"
    
    (n - 1 - pass).times do |i|
      if array[i] > array[i + 1]
        array[i], array[i + 1] = array[i + 1], array[i]
        swapped = true
        puts "  Swapped #{array[i + 1]} and #{array[i]}: #{array}"
      end
    end
    
    break unless swapped
    pass += 1
  end
  
  puts "\nFinal: #{array}"
  array
end

demonstrate_bubble_sort
# Original: [5, 2, 8, 1, 9]
# Pass 1:
#   Swapped 5 and 2: [2, 5, 8, 1, 9]
#   Swapped 8 and 1: [2, 5, 1, 8, 9]
# Pass 2:
#   Swapped 5 and 1: [2, 1, 5, 8, 9]
# Pass 3:
#   Swapped 2 and 1: [1, 2, 5, 8, 9]
# Final: [1, 2, 5, 8, 9]

Selection sort visualization:

def demonstrate_selection_sort
  array = [64, 25, 12, 22, 11]
  puts "Original: #{array}"
  n = array.length
  
  (n - 1).times do |i|
    min_index = i
    puts "\nIteration #{i + 1}:"
    puts "  Sorted region: #{array[0...i]}" if i > 0
    puts "  Finding minimum in: #{array[i...n]}"
    
    (i + 1...n).each do |j|
      if array[j] < array[min_index]
        min_index = j
        puts "    New minimum: #{array[j]} at index #{j}"
      end
    end
    
    if i != min_index
      puts "  Swapping #{array[i]} with #{array[min_index]}"
      array[i], array[min_index] = array[min_index], array[i]
    end
    puts "  Array: #{array}"
  end
  
  puts "\nFinal: #{array}"
  array
end

demonstrate_selection_sort
# Original: [64, 25, 12, 22, 11]
# Iteration 1:
#   Finding minimum in: [64, 25, 12, 22, 11]
#     New minimum: 25 at index 1
#     New minimum: 12 at index 2
#     New minimum: 11 at index 4
#   Swapping 64 with 11
#   Array: [11, 25, 12, 22, 64]

Sorting objects by multiple criteria:

Employee = Struct.new(:name, :department, :salary)

employees = [
  Employee.new("Alice", "Engineering", 90000),
  Employee.new("Bob", "Engineering", 85000),
  Employee.new("Charlie", "Sales", 75000),
  Employee.new("Diana", "Engineering", 95000)
]

def sort_employees_by_salary(employees)
  n = employees.length
  
  (n - 1).times do |i|
    min_index = i
    
    (i + 1...n).each do |j|
      if employees[j].salary < employees[min_index].salary
        min_index = j
      end
    end
    
    employees[i], employees[min_index] = employees[min_index], employees[i]
  end
  
  employees
end

sorted = sort_employees_by_salary(employees)
sorted.each { |e| puts "#{e.name}: $#{e.salary}" }
# Charlie: $75000
# Bob: $85000
# Alice: $90000
# Diana: $95000

Sorting strings by custom rules:

def sort_strings_case_insensitive(strings)
  n = strings.length
  
  (n - 1).times do |pass|
    swapped = false
    
    (n - 1 - pass).times do |i|
      if strings[i].downcase > strings[i + 1].downcase
        strings[i], strings[i + 1] = strings[i + 1], strings[i]
        swapped = true
      end
    end
    
    break unless swapped
  end
  
  strings
end

words = ["Zebra", "apple", "Mango", "berry", "Apple"]
sort_strings_case_insensitive(words)
# => ["apple", "Apple", "berry", "Mango", "Zebra"]

Partial sorting to find top N elements:

def find_top_n_with_selection(array, n)
  n = [n, array.length].min
  
  n.times do |i|
    max_index = i
    
    (i + 1...array.length).each do |j|
      max_index = j if array[j] > array[max_index]
    end
    
    array[i], array[max_index] = array[max_index], array[i]
  end
  
  array[0...n]
end

scores = [78, 92, 65, 88, 95, 71, 84]
top_3 = find_top_n_with_selection(scores, 3)
# => [95, 92, 88]

Design Considerations

The choice between bubble sort and selection sort depends on the specific constraints and characteristics of the sorting task. Neither algorithm performs well on large datasets, but they excel in different scenarios based on their operational characteristics.

Selection sort makes fewer swaps than bubble sort. The algorithm performs at most n-1 swaps for an array of n elements, with each swap placing an element in its final position. This property matters when swap operations are expensive, such as when sorting large objects, records in a database, or elements stored on slow media. Bubble sort can require O(n²) swaps in the worst case, making it unsuitable when swaps are costly.

Bubble sort adapts to partially sorted input through its early termination optimization. When the array is nearly sorted, bubble sort completes in close to linear time. Selection sort performs the same number of comparisons regardless of initial ordering, making it unsuitable for maintaining nearly-sorted data or responding to small perturbations in sorted arrays.

Memory constraints favor both algorithms equally. Both operate in-place with O(1) space complexity, making them suitable for embedded systems, microcontrollers, or any environment where available memory is limited. The choice between them in memory-constrained environments depends on other factors such as swap cost.

Stability requirements influence algorithm selection. Bubble sort maintains the relative order of equal elements when implemented correctly. Selection sort requires modification to achieve stability, adding complexity to the implementation. Applications that require stability, such as multi-level sorting or sorting records with secondary keys, favor bubble sort.

Input size represents the primary selection criterion. Both algorithms degrade to O(n²) time complexity on larger inputs, making them impractical for arrays exceeding a few dozen elements. For arrays smaller than 10-20 elements, the simplicity of these algorithms outweighs their poor asymptotic complexity. The constant factors in their performance become irrelevant at small scales.

Educational contexts favor these algorithms for demonstrating sorting concepts. Bubble sort introduces the idea of optimization through early termination and shows how algorithms can adapt to input characteristics. Selection sort demonstrates the maintain-sorted-region strategy that appears in more sophisticated algorithms like heapsort.

Testing and debugging scenarios sometimes use these algorithms because their simplicity makes correctness easy to verify. When validating a sorting framework or comparison function, implementing a simple sorting algorithm first confirms that the infrastructure works correctly before introducing more complex algorithms.

Hardware with specialized comparison or swap operations might favor one algorithm over the other. Systems with fast comparison but slow swap operations benefit from selection sort's minimal swap count. Systems with pipelined or vectorized comparison operations might optimize bubble sort's adjacent comparisons more effectively.

Performance Considerations

Time complexity analysis reveals fundamental performance limitations. Bubble sort and selection sort both exhibit O(n²) time complexity in the worst and average cases, performing approximately n²/2 comparisons and up to n²/2 swaps. This quadratic growth makes them impractical for large datasets, where n represents the number of elements.

Bubble sort's best-case performance reaches O(n) when the input is already sorted, assuming the early termination optimization is implemented. A single pass through the array confirms no swaps are needed. Selection sort maintains O(n²) complexity regardless of input ordering because it always scans the entire unsorted region to find the minimum element.

The constant factors differ between algorithms. Selection sort performs approximately n²/2 comparisons and at most n swaps. Bubble sort performs approximately n²/2 comparisons and up to n²/2 swaps in the worst case. The ratio of comparison time to swap time determines which algorithm performs better for specific data types.

Cache performance affects both algorithms differently. Bubble sort accesses adjacent elements sequentially, exhibiting good spatial locality. Modern processors cache sequential memory access efficiently, potentially improving bubble sort's performance. Selection sort scans the entire unsorted region during each iteration, creating less predictable memory access patterns.

Branch prediction impacts bubble sort more significantly than selection sort. The conditional swap in bubble sort creates branch mispredictions when the array contains random data. Modern processors predict branches based on recent history, but random comparisons reduce prediction accuracy. Selection sort separates the minimum-finding phase from the swap operation, reducing branch prediction penalties.

Comparison count versus swap count creates different performance profiles. When comparisons are cheap and swaps are expensive, selection sort's O(n) swap bound provides substantial advantages. When swaps are cheap, bubble sort's potential for early termination in nearly-sorted cases becomes valuable.

Benchmarking reveals performance characteristics:

require 'benchmark'

def generate_random_array(size)
  Array.new(size) { rand(1..1000) }
end

sizes = [10, 50, 100, 500, 1000]

sizes.each do |size|
  array = generate_random_array(size)
  
  Benchmark.bm(20) do |x|
    x.report("Bubble sort (#{size}):") do
      bubble_sort_optimized(array.dup)
    end
    
    x.report("Selection sort (#{size}):") do
      selection_sort(array.dup)
    end
    
    x.report("Ruby sort (#{size}):") do
      array.dup.sort
    end
  end
  puts
end

Execution counts demonstrate algorithmic differences. For an array of 5 elements [5, 2, 8, 1, 9], bubble sort performs 10 comparisons and 6 swaps in the worst case. Selection sort performs 10 comparisons and 4 swaps. The difference becomes more pronounced as array size increases.

Optimization opportunities exist within constraints. Bubble sort benefits from tracking the position of the last swap, allowing subsequent passes to ignore the sorted tail. Cocktail sort, a variant of bubble sort, alternates between forward and backward passes to move elements toward both ends simultaneously.

Selection sort offers limited optimization opportunities. The algorithm can be modified to find both minimum and maximum elements in each pass, sorting from both ends simultaneously. This optimization reduces the number of passes by half but maintains O(n²) time complexity.

Input characteristics dramatically affect performance. Nearly sorted arrays favor bubble sort with early termination. Reverse-sorted arrays represent the worst case for both algorithms, requiring maximum comparisons and swaps. Random arrays perform somewhere between best and worst cases, typically closer to worst-case behavior.

Common Pitfalls

Off-by-one errors in loop bounds cause incorrect sorting or array index violations. The outer loop should iterate n-1 times, not n times, because the last element is automatically in place after sorting the first n-1 elements. The inner loop must account for the current pass number to avoid comparing beyond the array bounds.

Incorrect loop bound in bubble sort:

# INCORRECT - causes out of bounds access
def bubble_sort_wrong(array)
  n = array.length
  
  n.times do |i|
    n.times do |j|  # Wrong: should be (n - 1 - i)
      if array[j] > array[j + 1]  # Crashes when j = n - 1
        array[j], array[j + 1] = array[j + 1], array[j]
      end
    end
  end
  
  array
end

Missing early termination in bubble sort reduces performance on nearly-sorted arrays. Without checking for swaps, the algorithm always performs n-1 passes regardless of input ordering:

# INEFFICIENT - no early termination
def bubble_sort_inefficient(array)
  n = array.length
  
  (n - 1).times do |pass|
    (n - 1 - pass).times do |i|
      if array[i] > array[i + 1]
        array[i], array[i + 1] = array[i + 1], array[i]
      end
    end
    # Missing: break unless swapped
  end
  
  array
end

Incorrect comparison operators produce unexpected results. Using greater than or equal (>=) instead of greater than (>) in bubble sort breaks stability by swapping equal elements:

# INCORRECT - breaks stability
def bubble_sort_unstable(array)
  n = array.length
  
  (n - 1).times do
    (n - 1).times do |i|
      if array[i] >= array[i + 1]  # Wrong: should be >
        array[i], array[i + 1] = array[i + 1], array[i]
      end
    end
  end
  
  array
end

Selection sort requires checking if the minimum index differs from the current index before swapping. Swapping an element with itself is unnecessary and can cause issues when sorting complex objects:

# INEFFICIENT - unnecessary swaps
def selection_sort_unnecessary_swaps(array)
  n = array.length
  
  (n - 1).times do |i|
    min_index = i
    
    (i + 1...n).each do |j|
      min_index = j if array[j] < array[min_index]
    end
    
    # Missing: if i != min_index
    array[i], array[min_index] = array[min_index], array[i]
  end
  
  array
end

Modifying the array during comparison operations causes undefined behavior. Custom comparison functions should not have side effects:

# DANGEROUS - modifies array during sort
counter = 0
array.sort! do |a, b|
  counter += 1  # Side effect
  a <=> b
end

Forgetting to handle nil values or mixed types causes comparison errors:

array = [3, nil, 1, 5]
bubble_sort(array)  # Raises NoMethodError: undefined method '>' for nil:NilClass

Correct handling requires nil checks:

def bubble_sort_with_nil(array)
  n = array.length
  
  (n - 1).times do |pass|
    swapped = false
    
    (n - 1 - pass).times do |i|
      next if array[i].nil? || array[i + 1].nil?
      
      if array[i] > array[i + 1]
        array[i], array[i + 1] = array[i + 1], array[i]
        swapped = true
      end
    end
    
    break unless swapped
  end
  
  array
end

Attempting to use these algorithms on large datasets causes performance issues. Arrays larger than a few hundred elements should use more efficient sorting algorithms:

# SLOW - inappropriate algorithm choice
large_array = Array.new(10_000) { rand(1..100_000) }
bubble_sort(large_array)  # Takes several seconds

Incorrect handling of custom objects without comparison operators defined:

class Person
  attr_accessor :name, :age
  
  def initialize(name, age)
    @name = name
    @age = age
  end
  # Missing: <=> operator or comparison logic
end

people = [Person.new("Alice", 30), Person.new("Bob", 25)]
bubble_sort(people)  # Raises NoMethodError: undefined method '>' for Person

Correct implementation requires defining comparison operators:

class Person
  attr_accessor :name, :age
  
  def initialize(name, age)
    @name = name
    @age = age
  end
  
  def <=>(other)
    age <=> other.age
  end
  
  def >(other)
    (self <=> other) > 0
  end
end

Reference

Algorithm Complexity

Operation Counts

Algorithm Characteristics

Implementation Patterns

Common Use Cases

Ruby Implementation Reference

Loop Structure Templates

Bubble sort template:

(n - 1).times do |pass|
  swapped = false
  (n - 1 - pass).times do |i|
    if array[i] > array[i + 1]
      array[i], array[i + 1] = array[i + 1], array[i]
      swapped = true
    end
  end
  break unless swapped
end

Selection sort template:

(n - 1).times do |i|
  min_index = i
  (i + 1...n).each do |j|
    min_index = j if array[j] < array[min_index]
  end
  array[i], array[min_index] = array[min_index], array[i] if i != min_index
end

Optimization Checklist

Common Mistakes