DEV Community

Megan
Megan

Posted on • Updated on

Quick Sort in Ruby

#ruby #tutorial #computerscience #beginners

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!

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.

Time Case
O(n log n) average case run time
O(n2) worst case run time

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.

Quick Sort Final Result

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.

Quick Sort Initial

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.

Quick Sort Swapping Values

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
Enter fullscreen mode Exit fullscreen mode

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:

quick sort videos:

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 😊

Top comments (5)

Collapse
 
kdraypole profile image
Kobe Raypole • • Edited

Congrats on finishing Flatiron! Your code looks great, but I agree with Matthieu. Part of writing good Ruby code is having the code explain itself by reading variable/method names. We write code for people, not computers:) I had an interesting thought. Since the only thing that we are sorting is an array, we could add this to the class to simplify things even farther down. It's generally not a good idea to modify ruby classes, but for the sake of learning I thought it would be interesting to try

class Array
  def quick_sort(from_index = 0, to_index = length - 1)
     if from_index < to_index
       pivot_index = partition_and_get_pivot_index(from_index, to_index)
       quick_sort(from_index, pivot_index - 1)
       quick_sort(pivot_index + 1, to_index)
     end
     return self
   end

   def partition_and_get_pivot_index(from_index, to_index)
     pivot_value = self[to_index]
     pointer_a_index = pointer_b_index = from_index

     while pointer_a_index < to_index
       if self[pointer_a_index] <= pivot_value
         swap_values(pointer_a_index, pointer_b_index)
         pointer_b_index += 1
       end
       pointer_a_index += 1
     end
     swap_values(pointer_b_index, to_index)
     return pointer_b_index
   end

   def swap_values(index_a, index_b)
     self[index_a], self[index_b] = self[index_b], self[index_a]
   end
end
Enter fullscreen mode Exit fullscreen mode

now if we have an array arr = [4, 3, 5, 1, 2]
we can run

arr.quick_sort 
# >> [1, 2, 3, 4, 5]
Enter fullscreen mode Exit fullscreen mode
Collapse
 
mwong068 profile image
Megan •

Thanks so much Kobe! 😊

That's an awesome thought, and I appreciate you sharing that implementation. It's definitely another great way to approach the problem!

Collapse
 
mdegoys profile image
Matthieu • • Edited

This is great, thanks for sharing :)

Also, if I may, I have three comments/questions about your code:

  • I think in ruby snake_case is preferred for method names (see github.com/rubocop-hq/ruby-style-g...)
  • I'm not sure to understand why the conversion to_i is needed in this line if array[i].to_i <= pivot.to_i as it seems to me the values are already integers ?
  • It was a little hard for me to understand the code as I didn't know about the algorithm. Maybe using variables names that reveal the intention would help make it easier to read ? For my own usage I just changed in your code the variables names, following your explanations, to help me understand : 
def quick_sort(array, from_index = 0, to_index = array.length - 1)
  if from_index < to_index
    pivot_index = partition_and_get_pivot_index(array, from_index, to_index)
    quick_sort(array, from_index, pivot_index - 1)
    quick_sort(array, pivot_index + 1, to_index)
  end
  return array
end

def partition_and_get_pivot_index(array, from_index, to_index)
  pivot_value = array[to_index]
  pointer_a_index = from_index
  pointer_b_index = from_index

  while pointer_a_index < to_index
    if array[pointer_a_index] <= pivot_value
      swap_values(array, pointer_a_index, pointer_b_index)
      pointer_b_index += 1
    end
    pointer_a_index += 1
  end
  swap_values(array, pointer_b_index, to_index)
  return pointer_b_index
end 

def swap_values(array, index_a, index_b)
  array[index_a], array[index_b] = array[index_b], array[index_a]
end
Collapse
 
mwong068 profile image
Megan • • Edited

Hey Matthieu! Thanks for the comments.

I appreciate you pointing out the snake_case, I've had a bit of trouble keeping those straight as I've been moving around in languages haha. I've corrected that in the code.

As for the conversion, I simply kept that line there in case anyone ran into problems. When I was testing the code in repl.it, the conversion to integer was necessary so I didn't want anyone to run into the same error as me.

And I love what you did with the renaming of the variables and creating the swapping function. I think that is really helpful and I'll definitely keep it in mind for my next article. Thanks again for your thoughtful discussion!

Collapse
 
valenciaw9 profile image
Valencia Walker •

Hi, I'm currently attending Flat Iron School for Software Engineering. Thank you for this article, it's so informative.

Read next

sahanonp profile image

How to setup Semantic Release with GitHub Actions.

Sahanon Phisetpakasit -

dhanushnehru profile image

What happens when you type a URL into your browser?

Dhanush N -

jaredcodes profile image

Finally Understand Responsive Design!

Jared Weiss -

necatiozmen profile image

Synch vs. Async Programming

Necati Özmen -