Quick Sort in Ruby

I graduated from Flatiron School! 🎉👩🏻‍🎓 It's been a little while since our showcase and graduation, but what an amazing journey it was 🥰 I took some time off from programming and studying to play a bit of Animal Crossing and relax. But this week my job search has officially begun and I thought, what better way of starting it off than with a series on sorting algorithms in Ruby.

As I've been learning data structures and algorithms as interview prep, I've found it quite difficult to find the resources I need to implement many of these concepts in Ruby. Because of this I thought it'd be lovely to start a sorting series in Ruby for anyone else who wants to use this dynamic, amazing language for their coding interviews. I've read a lot of articles on techniques that should be studied for the coding interview, and I've yet to find one that doesn't recommend knowing at least a few sorting algorithms. So I hope you find this series helpful and please leave comments below if you have anything to add. Thanks and enjoy!
<% @collection.articles.published.order("published_at ASC").each_with_index do |article, i| %>
So the first of the series I'd like to begin with is quick sort.

Overview

First, a little overview about the quick sort algorithm:

• Quick sort follows the "divide and conquer" strategy
  • which is basically to say that the problem gets broken down into sub-problems and these sub-problems are solved to create the final solution
• It is an algorithm that deals with recursion
  • everyone's favorite, but if you don't know what that is or need a little refresher, I'll link a few resources at the bottom of this post and maybe I'll even write my own post later on!
• Quick sort is an in-place sorting algorithm
  • essentially, we won't have to create a new array, but quick sort will manipulate the original array itself. that doesn't seem important now but it really contributes to what we'll talk about next...

Time Complexity!

Like every good algorithm that would ever be needed in any good coding interview, we have to discuss the time complexity.

Although worst case is very slow, quick sort is actually usually the most practical choice for an implementation of a sorting algorithm when solving problems. And a fun fact is that most of the sort functions in different languages actually use some form of quick sort!

Theory/Break Down

Alright, let's go into the theory behind the quick sort algorithm. When I say theory I find it the most helpful to visualize what the actual process is and then we can code it up.

The basic idea of quick sort is that the array is broken up into two halves, or partitioned, with a chosen number, the pivot, as the middle value in between both of the halves. This is done recursively, or over and over again on the smaller halves that are created until the array is sorted.

The pivot value can be any number in the array, but in this implementation we will use the last element. The pivot value is used to compare against the other values in the array, the lower values being kept in the left half and the higher values being kept in the right half. This is done by using two pointers, let's call them A and B, both starting at the beginning of the array and moving towards the end.

A moves down the array until it finds a value smaller than the pivot and B does not move until A encounters a smaller value. When A finds this value, it swaps it's value with B's value, and then B is incremented. This pattern continues until A reaches the end, and then the last value in the array, or the pivot, is swapped with the value at B. This is to ensure that the pivot value always ends up where it belongs.

Actual Code

Alright, on to the part you've been probably waiting for, the code! This is just my implementation of quick sort in Ruby and you can feel free to play with it and change it around to whatever works best for you.

def quick_sort(array, first, last)
  if first < last
    j = partition(array, first, last)
    quick_sort(array, first, j-1)
    quick_sort(array, j+1, last)
  end
  return array
end

def partition(array, first, last)
  pivot = array[last]
  pIndex = first
  i = first
    while i < last
      if array[i].to_i <= pivot.to_i
        array[i], array[pIndex] = array[pIndex], array[i]
        pIndex += 1
      end
    i += 1
    end
    array[pIndex], array[last] = array[last], array[pIndex]
    return pIndex
end 

For a little clarification in the code and to match the theory that was previously explained, pointer A would be represented by i and pointer B would be represented by pIndex (or partition index). First we have our method quick sort, which calls on the function partition once and then on itself twice. The partition function is used to break the array into the halves and then quick sort is called again on the new halves until there are no halves left. This will then return our sorted array.

Resources

Here are a few helpful resources in case you want to see the quick sort algorithm in action or if you need a little refresher on recursion:

recursion:

• https://www.geeksforgeeks.org/recursion/

quick sort videos:

• https://www.youtube.com/watch?v=COk73cpQbFQ
• https://www.youtube.com/watch?v=7h1s2SojIRw

I hope that this could be helpful for you and I'll catch you for the next installment of my sorting algorithm series! Happy coding 😊