Implementing Quicksort

A few weeks ago, Ian Douglas asked me to help give mock technical interviews for Turing students. As someone coming out of a code school, tech interviews are the emotional equivalent of walking into Mordor. They're absolutely horrifying. (Full disclosure: I cry after every tech interview. And then drink heavily. I can't be the only one.)

I've been thinking a lot about the questions asked lately. And, unsurprisingly to you, O(n) and sorts come up frequently. I'm not going to go into too much detail about O(n) because, frankly, I don't feel qualified. Greek symbols in math scare me. They're like warning signs for the rest of us. 

For developers, the purpose of these questions is to measure your understanding of time complexity — the length of time your algorithm (function, method, code) takes to process the result.

O(n) refers to linear time. The algorithm will take more time proportionate to the size of the input. 

Sample Problem

Let's take an interview question like: Write a function that takes a list of integers and returns it from least to greatest in O(n) time. Godspeed if you have to do this on a whiteboard. Sending good thoughts your way. 

Sorts have always fascinated me and I don't know much about them so it's a great opportunity to learn something new. (If you haven't seen the Hungarian folk dance of bubble sort, you're missing out.)

I'm the first to admit that computer science fundamentals are a growth area for me. I'm far from an expert in the area of well-known algorithms. A little googling and I found that the most reliably linear algorithm for sorting is quicksort. Awesome. (I should say here that algorithms are always evaluated on worst-case scenario. And in worst-case, quicksort is not O(n). That said, it's pretty darn good.)

A little more googling and it turns out quicksort should be called hardestsort. But I decided to give it a shot anyway. 

An article on DevCamp gave me a start. But, Ruby's syntactic sugar was too much for me. I couldn't tell what was happening. This solution is beautiful, but I need to keep looking.

This StackOverflow post (note the verbose quicksort algorithm toward the bottom) led me to Khan Academy and helped me break down what exactly is happening. 

Here's how quicksort works:

1. You have a list. Yay for arrays!

2. You choose a pivot point. This is an index in the list you'll use to split the array into three parts: the left array, the pivot and the right array. From my research, I've seen the pivot selected randomly, as well as first or last index being used. Let's talk about this using the first item in the array as the pivot.

3. Compare the pivot to the value to its right. If the pivot is smaller than its neighbor, leave it. If the pivot is larger than the value to the right, switch their positions.

4. Buckle up for recursion. Move the pivot and do the same thing.

Handcrafted Quicksort

Let's dive into some code. 

If you're still confused about what's happening, let's look at the output. This is the list each time we call quicksort(). I added a bit of color whenever two values are swapped.

$ quicksort([0, 7, 0, 87, 4567, 18, 65, 55, 55, 99, 987, 2345678, 0, 1, 10000])

Pretty cool, huh? 

Fancy Quicksort

OK, I feel like I have much more of a grasp of what's actually happening. I'd be lying if I said I could deliver an hour-long lecture about it, but I'm learning!

I wanted to revisit the "elegant" version I saw before. And found this lovely video.

To the code, Batman! 

This implementation involves meta-programming (I'm a little nervous about this) and extending the Array class. 

OMG is that so much better that the first go. 

Remember how we pass the block in with the less than symbol? This sorts the numbers greatest to least. If you were to call partition(&pivot.method(:>)) instead, it would sort the values least to greatest.  

For more reading on the partition method, check out the docs. 

I sincerely hope this helps you on your next interview question on sorting. But like I said, if you're at the whiteboard, I'm sorry. Good luck!

Recursively Replicating Ruby's Flatten Method

You can view the full .flatten method challenge here.

Flatten Challenge

The flatten method is a handy tool to compress nested arrays into one, flat array without losing any of the data. It works like this:

> [[1, 3], [5, [7, 9]]].flatten
=> [1, 3, 5, 7, 9]

Instead of relying on the .flatten method in Ruby, we'll build our own recursively. 

TDD

I'll start by building a test.

require 'minitest'
require 'minitest/autorun'
require 'minitest/pride'
require '../flatten'

class FlattenTest < Minitest::Test

  def test_combine_nested_arrays
    all = [1, 1, 2, 3, 4, 5]
    start_array = [1, [1,2],[3,[4,5]]]

    assert_equal all, CustomArray.new.combine_nested_arrays(start_array)
  end

I'm always skeptical of tests that run correctly the first time, so I prefer to run each test, expecting it to fail, before I proceed. 

Now it's time to start building the method. 

My first thought is that I'll need to iterate through each nested array and flatten it before proceeding to the next nested array.

Let's set up the class file.

  require 'pry'

  class CustomFlattenMethod
    def need_a_method
    end
  end

The most efficient way I can think to do this would be to pull the data out of the nested array and shovel it into another array. 

I'll call the flatten method `combine_nested_arrays`.

The Method

I'll walk through it step-by-step below. 

  attr_reader :all

  def combine_nested_arrays(arr, all=[])
    arr.each do |item|
      if item.class != Array
        all << item
      else
        combine_nested_arrays(item, all)
      end
    end
    all
  end

I set the variable `all` to default to an empty array. That way the method will be able to receive one or two variables, both arrays. One to flatten and another (the default `all`) to push our data into. 

  def combine_nested_arrays(arr, all=[])

Then we want to iterate through the array containing the nested arrays and pull out the data from each nested array.

  arr.each do |item|

However, what happens if one of the items in the array isn't an array?

For example, what if our array looked like this:

> [2, [1, 3], [5, [7, 9]]]

The first number, 2, isn't an array, it's just an integer. I'll set up an if/then statement to manage this situation. 

  arr.each do |item|
    if item.class != Array
      all << item
    else
      combine_nested_arrays(item, all)
    end
  end

Now if the item being altered within our iteration isn't an array, it will automatically be shoveled into our new array, `all`. It doesn't matter if it's an integer, symbol or string.

Recursive Magic

If the item is an array, magic happens. 

Not really, but we do recursively solve the problem. An array is sent back into our method, `combine_nested_arrays`. 

A nested array will be sent back through the method until the item being item in the iteration is no longer an array. 

If the first item in the original array was an array, the parameter `all` will continue to be it's default `all = []` when it's sent through the method again.

However, if the first item is not an array, and `all` is no longer an empty array, that array will be passed into the method along with `arr`.

More Tests

Because I'm a fan of tests, I wrote some more, along with a few edge cases, to confirm my assumptions were correct. 

Below is my full test suite. 

  require 'minitest'
  require 'minitest/autorun'
  require 'minitest/pride'
  require '../flatten'

  class FlattenTest < Minitest::Test

    def test_combine_nested_arrays
      all = [1, 1, 2, 3, 4, 5]
      start_array = [1, [1,2],[3,[4,5]]]

      assert_equal all, CustomArray.new.combine_nested_arrays(start_array)
    end

    def test_combine_nested_arrays_start_with_array
      all = [1, 2, 3, 4, 5]
      start_array = [[1,2],[3,[4,5]]]

      assert_equal all, CustomArray.new.combine_nested_arrays(start_array)
    end

    def test_combine_nested_arrays_start_with_array_nested_nested
      all = [1, 2, 3, 4, 3, 4, 5]
      start_array = [[1, 2, [3, 4]],[3,[4,5]]]

      assert_equal all, CustomArray.new.combine_nested_arrays(start_array)
    end

    def test_combine_nested_arrays_differet_type_data
      all = [1, "2", 3, 4, 3, 4, 5]
      start_array = [[1, "2", [3, 4]],[3,[4,5]]]

      assert_equal all, CustomArray.new.combine_nested_arrays(start_array)
    end

  end

Want to play with the code? View this repository on Github.

Recursion + Factorials

Quick shoutout to Natasha the Robot for her excellent writeup.

“Recursion is one of the most elegant things I don’t fully understand.
”

Recursion is beautiful. It's a bit like the movie Inception, in which everyone is in a dream within a dream.

In other words, a recursive method calls itself with new variables and continues to do so until the problem is solved, the method is told to break or your computer crashes. 

It's important to note that while a loop also continues to do something until it's forced to stop, loops are iterators and are not recursive in nature. 

Factorials

One of the problems best solved through a recursive method is finding the factorial of a number, which is denoted as the number, followed by an exclamation point (e.g. 5!). 

Factorial Iteration vs. Recursion

When I first approached the problem, I kept fighting the urge to iterate over the numbers. I blame Ruby's excellent flexibility. 

While you can find the factorial of a number, it's more elegantly coded as a recursive method. 

Nevertheless, here's an example of how you could iterate to find the factorial of a number:

You can read more about the #inject method in the Ruby docs.

 

Potential Problems

Negative numbers

Factorials of negative numbers are undefined. (I'm not a mathematician, but you can read more about there here.)

When I create a recursive method that takes input from the user, I'll have to make sure they submit a positive integer or natural number (in this case, I'm including zero as a natural number). 

The iteration currently doesn't account for this. It simply returns nil.

ZERO

The factorial of zero is one (0! = 1). If that's confusing to you, as it was to me, here's a brief explanation. 

1! = 1

2! = 2

3! = 6

4! = 24

If you're thinking, "Well, duh, get to the point," bear with me. 

Let's take a different approach. 

3! = 4!/4

In other words, 3! = 24/4, which can be further simplified to 3! = 6. 

OK, awesome. Let's do the rest.

2! = 3!/3 = 2

1! = 2!/2 = 1

Here's the kicker:

0! = 1!/1 = 1

Neat, huh? So, if the user inputs zero, I'll have to ensure the method returns one. The iteration below doesn't account for this.

Getting Started

I wrote some pseudocode of what I wanted to accomplish before I started coding. 

START program

GET input from user, convert string to integer

IF input == 0, RETURN 1

LOOP

IF input < 0, ask user for another input

END LOOP

RETURN factorial of input

END program

User prompt method

I created a simple method to add "=> " in front of any message. It will allow the user to more easily see messages and prevent me from having a hundred `puts` in my program. 

Welcome to Factorial!

I started the program off with a simple welcome message and asked the user to input a positive integer. 

User Input + Verification

I had to define the variable outside of the loop, so I set `user_input` to zero. 

When the user inputs a number, I convert it to an integer and check if it's a number greater than zero using the `is_valid?` method. 

If the number is negative, `is_valid?` returns a false and the loop tells the user it's not a valid number. 

stack level too deep

If you allowed the user to input a negative number using this recursive method, it wouldn't return nil. 

Instead, it would return an error: stack level too deep (SystemStackError). 

Though it returns the error within a second, the computer can't process the amount of information you've put on top of the memory stack.

Basically, you've asked it to compute too much information and it's politely saying no. 

Recursive Method

And now the fun part. First, the `factorial` method determines if `user_input` is equal to zero. If it is, it returns a one. 

If it's not, it begins recursively problem-solving. 

As you can see above, the recursive method takes a number and multiplies it by the recursive method minus one. 

Visualizing Recursion

Returning the factorial

The final step is to let the user know the factorial of the value they inputed. 

The Full Program

See room for improvement? You can grab this factorial program on GitHub.

Or, shoot me an email. I'd love your feedback!