This time we delve into the merry world of ‘Sorting’ algorithms. First up on the menu is Bubble Sort. By no means is this an efficient sorting algorithm but it definitely is one of the easier to translate from theory to code.
Definition: sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted ~Wikipedia
To get a better understanding, consider an array (n) with 10 elements, ie. 3,0,1,8,7,2,5,4,6,9. One can clearly see that it is not in order at all (that is ascending). As such, following the bubble sort approach, we will compare every element on the left, to the element of the array on the right. When the element on the right is smaller then the element on the left, we will swap places. This again is a rinse and repeat until the process of sorting is complete. But not quite! An optimization to the algorithm is that after every iteration of sorting and swapping, the numbers on the extreme right are already sorted, called this ‘k’. As such, when we go through each iteration, we also increase k by 1, that is the remaining subsets of numbers at the end of the array or on the right hand that are already ordered and that we don’t need to even consider for swapping, and thus ignore in each iteration.
From “Start” to “Iteration X” you will see the flow of Bubble Sort as it makes it’s way. If you are still unclear, then I’ve done a terrible job of explaining something rather simple, and perhaps I can offer you this as a further explanation which is tremendous fun.
In terms of code, I’ve used the algorithm in Christopher Fox’s Concise Notes, which is publicly available on the Internet. It’s elegant and just darn efficient.
Before we dive into the code, Bubble Sort again is not efficient, but for small input sizes this may be just the thing you need. By way of Big O Notation, this algorithm is Big O(n*n) or O(n²).
describe Sorting::BubbleSort do before :each do @some_array = [3,2,1] @some_other_array = [2,4,51,23,45,1,17,20] @bs = Sorting::BubbleSort.new end context 'sort an array of numbers' do it 'should array of numbers' do expect(@bs.bubble_sort(@some_array)).to eq [1,2,3] expect(@bs.bubble_sort(@some_other_array)).to eq @some_other_array.sort end end end
class Sorting class BubbleSort def bubble_sort(array) (array.size - 1).downto(1).each do |k| 1.upto(k).each do |n| if array[n] < array[n - 1] array[n], array[n - 1] = array[n - 1], array[n] end end end array end end end
Code as always can be found here.