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²).

Rspec:

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

Code:

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.

In the first part of the topic of Trie, we layed out the fundamentals of what it is and semantics of the source code. But you can’t get maximum benefit from the Trie without the functionality of searching.

The first implementation of a search will be simply searching for an exact match of the word in the trie. Consider searching for the word ‘aces’. To begin search, we would need to break down the word into individual characters, and in a indexed loop, check if our Hash contains the matching key. So our first character would be ‘a’, and we would then progress to determine if at the heighest level, the key itself is ‘a’; which we can see is true from the diagram above. We will then move to or if you prefer retrieve the child of ‘a’. We will iterate in our loop to the next character in the word ‘aces’ which would be ‘c’. As before, we will determine if at that height the key has the matching character ‘c’. Again in light of the diagram that proves true and we will rinse and repeat, and thus find the ‘aces’ character by character. However, if in the process instead of ‘e’ (in aces), we find a key of ‘k’, that would mean the word does not exist, and we would return nil.

Here’s the code to which this would make more sense.

private
    def search_node(string)
      children = @root.children
      trienode = TrieNode.new
      string.split('').each_with_index do |char, index|
        if children.has_key?(char)
          trienode = children[char]
          children = trienode.children
        else
          return nil
        end
      end
      trienode
    end

We can also apply another form of search, that is ‘starts_with’ to find a matching prefix in a Trie of words. For example, our Trie has ‘aces, acer and actor’, we would want to determine if the following prefix ‘act’ exists. The concept is exactly the same as above with the word search as you will see in the code below. I’ve included all the pieces including Rspec.

context 'search' do
    before :each do
      @trie.insert('ace') # initial prefix
      @trie.insert('acer')
      @trie.insert('aces')
      @trie.insert('actor')
    end

    it 'should determine if a word exists in the trie' do
      expect(@trie.search('aces')).to eq true
    end

    it 'should return false if the word does not exist in the trie' do
      expect(@trie.search('ant')).to eq false
    end

    it 'should determine if there is any word in the trie that starts with the given prefix' do
      expect(@trie.starts_with('act')).to eq true
    end
  end

The full code:

def search(word)
      trienode = search_node(word)
      return true if (not trienode.nil? and trienode.is_leaf)
      false
    end

    def starts_with(prefix)
      return false if search_node(prefix).nil?
      true
    end

Stack concept

 

Firstly before delving into the code, let’s get a handle on the definition of a Stack.

According to Wikipedia:

“The stack is the memory set aside as scratch space for a thread of execution. When a function is called, a block is reserved on the top of the stack for local variables and some bookkeeping data. When that function returns, the block becomes unused and can be used the next time a function is called. The stack is always reserved in a LIFO (last in first out) order; the most recently reserved block is always the next block to be freed. This makes it really simple to keep track of the stack; freeing a block from the stack is nothing more than adjusting one pointer.”

A stack has some attributes that helps clarify it’s purpose and perhaps it’s definition. Consider a stack simply literally, as taking bricks and placing one on top of another. In coming back to this pile of brick, the most efficient way to access the next brick would be to reach for the one top-most. So too with a stack, it’s always concerned about the top. Whether adding or removing, all interactions happen at the top. This is called LIFO – last in, first out. Last brick in, is the last brick out. Stacks call, the removing of a brick (popping or POP) and the adding of a brick (pushing or PUSH).

So a stack has the following attributes:

  • LIFO – last in first out
  • Push – to add something onto the stack
  • Pop – to remove something from the stack

To dig a little deeper and bring out more about this peculiar thing called a stack, let us associate a stack to that of toddler stacking cups. Yes you’ve seen those. They look like this.

Stacking cups

A stack is simply the toddler placing these cups one on top of another. The cups slot into one another and provide a wide-rim for the next cup to slide onto and position itself. Now bear with me, let’s now call each cup (like the green one above), a Node. Why a node? Let’s consider a node in a tree, or rather the attributes of a node. A node (cup) has a colour of it’s own (a value) but also links to the next cup below it. Hold on a minute, this inter-linking should raise an alarm, yes, well done! This introduces another important concept with a stack, a Linked List. 

What is a Linked List?

A linked list is as we described above, ‘is a simple object (we’ll call it a Node) which has its own value or data, plus a pointer to the next Node in the list’.

In the image below, the first joined block is a node, with the first block being the value 12. The second block being a pointer, the location to the next node. But, and I say but, when you access that pointer, you don’t get back the pointer itself, but the actual node to which it’s linked. This is the beauty!

Linked list

How does a Linked List then relate back to a Stack? A linked list is the individual cups (blue, green, red, yellow above), and placing one on top of another (linking them), is called a “Stack”.

So what does the code look like?

A Linked List example:

class Node
  attr_accessor :value, :next_node

  def initialize(value, next_node)
    @value = value
    @next_node = next_node
  end
end

The code above simply provides us the mechanism for a Linked List. Now it’s interesting to note that Ruby doesn’t have a Linked List Data Type (as far as I know), because the functionality is built into Array. We get the same functionality using Array#shift (pop) and Array#unshift (push), however the difference here being that the focus is not on the top but on the bottom. Secondly, the advantage to this, is that you get Linked List functionality with the hybrid data access of an Array. By that I mean, an Array is great for getting random access to large data. A Linked list is purposeful when manipulating, inserting, deleting or re-ordering elements.

A Stack example:

class Stack
  def initialize
    @current = nil
  end

  def pop
    raise 'Stack is empty' if is_empty?
    top_of_stack = @current
    @current = top_of_stack.next_node
    top_of_stack.value 
  end

  def push(value)
    @current = Node.new(value, @current)
  end

  def is_empty?
    @current.nil?
  end
end

This is the output from interacting with the code in IRB:

Stack irb2

Credits:

I’ve regurgitated all this 😉

  1. Ruby Missing Datastructure
  2. Stack vs Heap (stack overflow)
  3. A Stack in Ruby using Linked Lists
  4. What is a Stack Data Structure (youtube)