bubble_sort_variants.rb

require 'benchmark'

def bubble_sort_1(array:)
    array = array.dup
    comparisons = 0
    array.length.times do
        i = 0
        while i < array.length  - 1
            if array[i] > array[i + 1]
                tmp = array[i + 1]
                array[i + 1] = array[i]
                array[i] = tmp
            end
            i += 1    
            comparisons += 1
        end
    end
    puts "bubble_sort_1: #{comparisons} comparisons"
    return array
end

def bubble_sort_2(array:)
    array = array.dup
    comparisons = 0
    maximum_number_of_comparisons = (array.length() -1) ** 2
    current_comparisons = 0
    while current_comparisons < maximum_number_of_comparisons
        i = 0
        while i < array.length  - 1
            if array[i] > array[i + 1]
                tmp = array[i + 1]
                array[i + 1] = array[i]
                array[i] = tmp
            end
            i += 1
            comparisons += 1
            current_comparisons += 1
        end
    end
    puts "bubble_sort_2: #{comparisons} comparisons"
    return array
end

def bubble_sort_3(array:)
    array = array.dup
    comparisons = 0
    swapped = nil
	while swapped || swapped == nil
		swapped = false
		i = 0
		while i < (array.length) - 1
			if array[i] > array[i + 1]   
			   array[i], array[i + 1] = array[i + 1], array[i]
			   swapped = true	
		    end
            comparisons +=1
			i += 1	
		end
	end
    puts "bubble_sort_3: #{comparisons} comparisons"
	return array
end

def bubble_sort_4(array:)
    array = array.dup
    comparisons = 0
    swapped = nil
    sorted_numbers = 0
	while swapped || swapped == nil
		swapped = false
		i = 0
          while i < (array.length) - (sorted_numbers + 1)
			if array[i] > array[i + 1]   
			   array[i], array[i + 1] = array[i + 1], array[i]
			   swapped = true	
		    end
            comparisons +=1
			i += 1
		end
        sorted_numbers += 1	
	end
    puts "bubble_sort_4: #{comparisons} comparisons"
	return array
end


numbers = 10_000.times.map {|_| rand(1..100_000)}
built_in_sort = numbers.dup.sort

# arr1 = bubble_sort_1(array: numbers)
# p arr1 == built_in_sort
# arr2 = bubble_sort_2(array: numbers)
# p arr2 == built_in_sort
# arr3 = bubble_sort_3(array: numbers)
# p arr3 == built_in_sort
# arr4 = bubble_sort_4(array: numbers)
# p arr4 == built_in_sort


puts Benchmark.measure { bubble_sort_1(array: numbers) }
puts Benchmark.measure { bubble_sort_2(array: numbers) }
puts Benchmark.measure { bubble_sort_3(array: numbers) }
puts Benchmark.measure { bubble_sort_4(array: numbers) }