Array Algorithms

array_reverse.rb

#
# 2 - REVERSAL
#
# The quickest way to reverse an array is to swap elements at either end, and repeat
# while moving up from the left and down from the right.
#
#   [ a b c d e f ]
#   [ f         a ] - Step 1 we switched A[0] with A[-1]
#   [   e     b   ] - Step 2 we switched A[1] with A[-2]
#   [     d c     ] - Step 3 we switched A[2] with A[-3]
#
# We can get the right number of iterations by dividing the array size in 2. 
# Ruby has intger based division, so if we have an odd number, say 7, the remainder is discarded.
# You can think of this as (7 / 2).floor, which is 3.
#
# This means in an odd sized array, the middle element stays the same when reversing the array.
#
#   [ a b c d e f g ]
#   [ g           a ] - Step 1 we switched A[0] with A[-1]
#   [   f       b   ] - Step 2 we switched A[1] with A[-2]
#   [     e   c     ] - Step 3 we switched A[2] with A[-3]
#   [       d       ] - Step 4 we switched A[3] with A[-4]
#
# This is essentially the same as switching elements with their opposites accross a series.
#
def reverse!(array)
  for i in 0...array.size / 2
    opposite_index = array.size - i - 1 
    array[i], array[opposite_index] = array[opposite_index], array[i]
  end
end

# Two things of note: We calculate the opposte index as array.size - 1 - i becase i will be 0 on the first iteration,
# and the array size always exceeds the index by in 0 based indecies. If we don't adjust this,
# we will be looking for a value that is out of bounds.
#
# Second, we can take advantage of parallel assignment in Ruby to switch the values without using
# a temporary variable. Sometimes this is not readable, so it's best to use a temp variable, other times it's fine.
#
# Contrast this to building a stack and poping the array on to the stack to acieve first out (of the array)
# first on (the new array).
#
def reverse_stack!(array)
  reversed = []
  reversed << array.pop until array.empty?
  reversed
end

a = [*"a".."e"]
b = reverse_stack!(a)
puts b.inspect

# Once more, we can make our first implementation more idiomatic by getting rid of the loop.
#
def reverse!(array)
  (0...array.size / 2).step do |i|
    opposite_index = array.size - i - 1
    array[i], array[opposite_index] = array[opposite_index], array[i]
  end
end

insertion_sort.rb

# Once we understand the fundamentals of rotating, other algorithms become easier to understand,
# and optimisations can become apparent when they were difficult to see first.
#
# For example, as we will see later, insertion sort depends on shifting elements,
# which is what we essentially implemented in rotate_left! and rotate_right!.
#
# But for now, let's see how our new understading helps rewrite our rotation algorithm to become O(m * n).
#
# thanks to Jerry Coffin for showing me this technique. (http://codereview.stackexchange.com/a/125226/1563)
#
def better_rotate!(array, steps = 1)
  (0...steps / 2).step do |i|
    array[i], array[steps - 1 - i] = array[steps - 1 - i], array[i]
  end

  (0...(array.size - steps) / 2).step do |i|
    array[i + steps], array[array.size - 1 - i] = array[array.size - 1 - i], array[i + steps]
  end

  (0...array.size / 2).step do |i|
    array[i], array[array.size - 1 - i] = array[array.size - 1 - i], array[i]
  end
end

a = [*"a".."e"]
better_rotate!(a)
puts a.inspect

# The only thing of note here is line 14 to 16. The first iteration starting on line 10 uses the same reversal algorithm
# we used to reverse the array. Except that it only reverses a portion of the array, starting at 0
# and ending on step - 1.
#
# The last part reverses the entire array. It's the same algorithm we used for reversing the entire array.
#
# The tricky part is the middle iteration. We want to reverse the array starting at step until array.size - 1.
# So we must offset the index of the first element by the number of steps, to make sure we are only operating in
# the second part of the array.
#
# Let's see if we can visualize this better. Assuming step = 2.
#
# The first step goes from 0...steps / 2, which is 0...(2 / 1), or 0...1, which 1 iteration (exclusive range).
#
#   [ a b c d e f g ]
#   [ b a           ] 
#
# The second step goes from 0...(array.size - steps) / 2), which is 0...((7 - 2) / 2), or 0...5 / 2, which is
# 0...2, or two iterations (exclusive range) of 0 and 1.
# 
# Since i starts at 0 (the beginning of the array), we want to offset it by the number of steps: 2, so it starts on the
# second part of the array.
#
# [ b a c d e f g ]
# [     g       c ] This is iteration 1, where i = 0. We switched array[i + step] with array[array.size - 1 - i].
#                   So array[0 + 2] with array[7 - 1 - 0]
#
# [       f   d   ] This is iteration 2, where i = 1. Again, we switched array[i + step] with array[array.size - 1 - i].
#                   So array[1 + 2] with array[7 - 1 - 1]
#
# At this point all that remains is e, and since this portion of the array is an odd number, it stays where it is.
#
# The final step is to reverse the entire array. This is what we have now.
#
#    [ b a g f e d c ]
#
# Once we reverse this, we will have the following:
#
#   [ b a g f e d c ]
#   [ c           b ] - Step 1 we switched A[0] with A[-1]
#   [   d       a   ] - Step 2 we switched A[1] with A[-2]
#   [     e   g     ] - Step 3 we switched A[2] with A[-3]
#   [       f       ] - Step 3 we switched A[3] with A[-4]
#
# If you start reading the array at A[-2] and continue right, you will see that
# it reads a, b, c, d, e, f.
#
# And their we have it; we rotated the array using our reverse algorithm, and reduced its asymptotic complexity.


# Before we get to Insertion sort, let's look at array insertion first (since, in order to sort using insertion,
# we should at least understand how insertion works). We'll assume that our array is sorted, and we want to insert
# a value in the correct order.
#
#   [ a b d e f g ]
#
def insert!(array, element)
  insert_at = array.size

  for i in 0...array.size
    if element < array[i]
      insert_at = i
      break
    end
  end

  array.size.downto(insert_at) do |j|
    array[j] = array[j - 1]
  end

  array[insert_at] = element
end

a = %w[a b d e f g]
insert!(a, "c")
puts a.inspect

# In order to insert an element at the right location, we have to find the index of the first element that's greater
# than our element. It makes things easier if we assume our element is greater than all of those in the
# array, so we default it to the array size, thereby inserting it as an extra element by default (if it is larger
# than all existing elements in the array).
#
# If and after we find this index, we want to shift all of the elements starting at this index to the end of the array
# by one to the right, creating a new element in the process.
#
# Once we do this, we can insert our element at the insertion index.
#
# This algorithm assumes that the array is already sorted.
#
# As usual, let's refactor this code and make it more idiomatic in the process. The first thing that stands out is the index
# finding procedure. We can extract that into its own method, and change from a loop to an enum.
#
def find_insertion_point(array, element)
  array.index { |e| element < e } || array.size
end

def insert!(array, element)
  insert_at = find_insertion_point(array, element)

  if insert_at < array.size
    array.size.downto(insert_at) do |j|
      array[j] = array[j - 1]
    end
  end

  array[insert_at] = element
end

# The only thing of interest here is the if statement. We only want to shift the elements by one to the right if
# insertion point is smaller than then array size (the element is smaller than the existing ones in the array).
#
# If the insertion point is equal to the array size, then the element should go last, and no shifting is
# necessary. If the insertion point is less, we should interate from the end of the array to the insertion point,
# shifting every element by one to the right.
#
# Finally, we insert the element at the insertion point.
#
# Let's visualize this to see how the algorithm looks. Assuming we start with [ a b d e f g ]
# and element is "c".
#
#   [ a > element ] Step 1, is array[0] greater than our element? No, continue.
#   [   b > element ] Step 2, is array[1] greater than our element? No, continue.
#   [     d > element ] Step 2, is array[2] greater than our element? Yes. This is our insertion index.
#
# No we move to shifting the array. At this point we have not mutated our array. We will iterate from array.size,
# (we use this to add new element to the array) to the insertion point. We'll call this j.
#
#   [ a b d e f g ] 
#   [           g g ] Step 1, get array[j - 1] and move it to array[j] (j = array.size).
#   [         f f g ] Step 2, get array[j - 2] and move it to array[j - 1].
#   [       e e f g ] Step 3, get array[j - 3] and move it to array[j - 2].
#   [     d d e f g ] Step 4, get array[j - 4] and move it to array[j - 3].
#   [ a b d d e f g ] 
#
# At this point we stop. Remember, we iterated down from array.size to the insertion point, or 6 to 2--4 steps.
# No we can insert the element at the insertion point.
#         .
#   [ a b c d e f g ] 
#
# We can make Ruby do all the work for us, of course. But where's the fun in that?
# (http://ruby-doc.org/core-2.2.0/Array.html#method-i-insert)
#
def insert!(array, element)
  insert_at = find_insertion_point(array, element)
  array.insert(insert_at, element)
end

# No we are ready to move onto insertion sort.

rotate_left.rb

#
# 1 - LEFT-RIGHT ROTATION
#
# There are several algorithms to rotate arrays, all with different asymptotic characteristics.
# Here are a few.

# This one has an O(m * n) where m is the number of steps and n is the size of the array.
# The procedure works by storing the first element, then shifting every other element down by one.
# Finally, we add the first element that we saved to the end of the array.
#
def rotate_left!(array, steps)
  for i in 0...steps
    first = array[0]
    for j in 1...array.size
      array[j - 1] = array[j]
    end
    array[-1] = first
  end
end

5.times do |i|
  a = [*"a".."e"]
  rotate_left!(a, i + 1)
  puts a.inspect
end

# Note that line 9 uses an exclusive range (...) because we have to start from 0 (since Ruby arrays are 0 index).
# Also note that the inner loop on line 11 always starts from 1. This is because, for each step, we
# always want to start from the second element in the array, which is at index 1.

# The following has O(n), which is more efficient, but it's much less readable.
#
# For this to work we have to think of the array in two parts, and reverse each part seprately. The split off point
# is the value of step. So given an array from 1..5, and where step = 3, we first reverse the elements from 0...3,
# and then we reverse elements from 3...array-size (not exclusive ranges). Finally, we reverse the entire array.
#
def array_rotate!(array, steps)
  for i in 0...steps / 2
    temp = array[i]
    array[i] = array[steps - i - 1]
    array[steps - i - 1] = temp
  end

  for j in steps...(array.size + steps) / 2
    temp = array[j]
    array[j] = array[array.size - 1 - (j - steps)]
    array[array.size - 1 - (j - steps)] = temp
  end

  for k in 0...array.size / 2
    temp = array[k]
    array[k] = array[array.size - 1 - k]
    array[array.size - 1 - k] = temp
  end
end

# We can implement those algorithms in simpler ways using the Ruby standard library.
#
# The following examples use the same technique: iterate the required number of steps, and on each step remove
# the first element (using array#shift) and add it as the last element (using array#push).
#
# The only difference between them is how the iteration is done: Using an enum or a loop.
#
def rotate_left!(array, steps)
  for i in 1..steps
    array.push(array.shift)
  end
end

def rotate_left(array, steps)
  steps.times { array.push(array.shift) }
end

def rotate_left(array, steps)
  steps.downto(0) { array.push(array.shift) }
end

def rotate_left!(array, steps)
  while steps > 0
    array.push(array.shift)
    steps -= 1
  end
end

def rotate_left!(array, steps)
  until steps <= 0
    array.push(array.shift)
    steps -= 1
  end
end

# It might be helpful to break down the procedure into two routines. This will shift left by one step.
# It iterates from 0 to array.size - 1, and on each step it stes the value of the current index, array[i]
# to the value of the next index, array[i + 1].
#
def rotate_left!(array)
  first = array[0]
  for i in 0...array.size
    array[i] = array[i + 1]
  end
  array[-1] = first
end

# We can make this more Ruby-line by using iterators instead of loops.
#
def rotate_left!(array)
  first = array.first
  (0...array.size).each { |i| array[i] = array[i + 1] }
  array[-1] = first
end

# To get this to shift by n steps, we can create a wrapper method.
#
def rotate_left_by!(array, steps = 1)
  steps.times { rotate_left!(array) }
end

# Breaking this down into two procedures makes reasoning about right-rotation even easier.
#
# We have to iterate backwards in order to avoid copying the same element over and over again.
# We set a temporary variable i to array.size - 1. We then iterate while i is less or equal to 0, decrementing it.
#
# On each iteration we want to set the value at the current index, array[i], to the value in the previous
# index, array[i - 1]. Essentially reversing what we did in left_rotate!.
#
# array[i] = array[i - 1] (right rotation) vs array[i] = array[i + 1] (left rotation).
# 
#
def rotate_right!(array)
  last = array[-1]
  i = array.size - 1
  while i >= 0
    array[i] = array[i - 1]
    i -= 1
  end
  array[0] = last
end

# Once more, we can make this more idiomatic Ruby by replacing loops with enumerators.
#
# Observe that we can't replace array[0] = last and array[-1] = first with push and unshift because they add
# new elements to either the front or the end of the array. We want to replace the elements in those locations,
# not add new ones to the array.
#
def rotate_right!(array)
  last = array.last
  (array.size - 1).downto(0) { |i| array[i] = array[i - 1] }
  array[0] = last
end

# Let's add a method to make rotating right by n steps more convenient.
#
def rotate_right_by!(array, steps)
  steps.times { rotate_right!(array) }
end

# The relationship between rotating right and left can be observed mathematically. It's an inverse
# operation in relation to the size of the array.
#
# When A = 5, L = 1 and R = 4. In other words, A = L + R, and using the inverse property
# R = A - L, and L = A - R.
#