For the last installment of Sorting algorithms in Ruby, I will be covering quicksort. This one is pretty famous, and a staple of CS classes.
Quicksort is a recursive sort algorithm that works by dividing the array to be sorted in two. An element called a pivot is then chosen. This element will be the one that determines how the array is next to be subdivided.
Different implementations of quicksort can use different methods for choosing the pivot. These will influence the performance of the algorithm itself. Choosing the first element as the pivot will result in bad performance on nearly sorted or already sorted arrays. Choosing the last element can also result in a similar case of poor performance.
A better implementation could be to choose the middle element or a random element. With the pivot choice, what you want to avoid is having the algorithm divide the sub-lists in a fashion as to create many sub-list with only one element, as this is wasteful.
Even so, my implementations will use the first element as it’s pivot for ease of implementation.
Here is how to algorithm works for the in-place version:
1. Divide the array in two.
2. Choose a pivot (in our case the first element of our divided array).
3. Using two indices, iterate on the sub array. One index will go from left to right, and the other right to left.
4. As the two indices iterate, swap the elements greater than the pivot to the right side of the sub array and the elements lesser than the pivot to the left side of the array.
5. Move the pivot where the two indices have crossed path.
Step 3, 4 and 5, are what is generally called the partition operation.
After step 5, the sub array will be divided in such a way that all elements smaller than the pivot will be left of the pivot and all elements greater than the pivot on it’s right side.
After that, you simply call quicksort on both side of the pivot to sort each of those two sub arrays.
This algorithm can be done in-place or out of place. As for the algorithms covered in previous posts, the out of place version is easier to implement but consumes more memory.
If performance is not an issue, or if you have trouble grasping the concept, I recommend starting with the out of place version. Once you understand it clearly, you can then implement the in-place version more easily. This technique applies for all sorting algorithms and I recommend it as a stepping stone for the more complex search algorithms.
The algorithm for the out of place version, is simpler. There is no need to muck around with indices. You just create two additional array at each recursive call. As you iterate you place the smaller elements in the first array and the greater elements in the other. You then call quicksort on both new arrays.
As in my last two posts, I will be using my generic sort test class to create the tests. I have created tests for both my in-place and out of place version of the algorithm. For brevity, I will only include one suite of tests.
require 'test/unit' require './quick_sort.rb' require './sort_test.rb' class QuickSortTest < Test::Unit::TestCase def setup quick_sort = QuickSort.new @sort_test = SortTest.new(quick_sort) end def test_empty_array assert @sort_test.test_empty_array, "Empty array not corectly sorted" end def test_array_with_one_element assert @sort_test.test_array_with_one_element, "Array with one element not correctly sorted" end def test_ordered_array assert @sort_test.test_ordered_array, "Ordered array not correctly sorted" end def test_array_with_even_number_of_elements assert @sort_test.test_array_with_even_number_of_elements, "Array with even number of elements not correctly sorted" end def test_array_with_odd_number_of_elements assert @sort_test.test_array_with_odd_number_of_elements, "Array with odd number of elements not correctly sorted" end def test_medium_sized_array assert @sort_test.test_medium_sized_array, "Medium sized array not correctly sorted" end def test_reversed_sorted_array assert @sort_test.test_reversed_sorted_array, "Reversed sorted array not correctly sorted" end def test_large_size_array assert @sort_test.test_large_sized_array, "Large sized array not correctly sorted" end def test_test_array_with_repeating_elements assert @sort_test.test_array_with_repeating_elements, "Array with repeating elements not correctly sorted" end end
Out of place
Here is the code for the out of place version:
class QuickSort def sort(to_sort) # stop the recursion if nothing to sort if to_sort.length <= 1 then return to_sort end # pick the pivot (I pick the last element) pivot = to_sort.pop # partition operation smaller_array =  larger_array =  to_sort.each do |element| if element <= pivot smaller_array.push(element) else larger_array.push(element) end end # recursively sort the sub arrays and concatenate the results return sort(smaller_array).push(pivot) + sort(larger_array) end end
While my in-place version picks the first element as the pivot, this one picks the last element for the convenience of using pop. Since there is no need to work with indices and swap elements around a pivot position, most of the complexity is done away with.
Here is the code for the in-place version:
class QuickSort def sort(to_sort, index_of_pivot = 0, right_index = to_sort.length - 1) old_right_index = right_index left_index = index_of_pivot # stop the recursion if nothing to sort if left_index >= right_index then return to_sort end # partition operation # move both indexes towards the center until they cross over # when left index finds an element greater than pivot and # right index finds an element smaller than pivot swap them while left_index < right_index while to_sort[left_index] <= to_sort[index_of_pivot] and left_index < to_sort.length - 1 left_index = left_index + 1 end right_index = right_index - 1 until to_sort[right_index] <= to_sort[index_of_pivot] # swap both elements if left_index < right_index to_sort[left_index], to_sort[right_index] = to_sort[right_index], to_sort[left_index] end end # swap pivot to_sort[index_of_pivot], to_sort[right_index] = to_sort[right_index], to_sort[index_of_pivot] # recursively sort the sub arrays sort(to_sort, index_of_pivot, right_index - 1) sort(to_sort, left_index, old_right_index) return to_sort end end
As you can see the in-place version is more complicated. The algorithm works on the array at hand by swapping elements. Since no new arrays are created, it works on subdivisions of the array represented by two indices: index_of_pivot (which also happens to be the left index) and right_index.
The partition operation will usually work several passes until the left and right index cross. Since both indices find and swap elements that should be on the other side of the array, when the two indices meet there are no more swaps necessary.
At that point all elements smaller than the pivot are to the left of where the pivot will end up. We then swap the pivot in it’s correct place and recursively sort both sides of the array.
As I mentioned in my first post of the series, I intended to cover some sorting algorithms in an OO language, which I just did, and then in a functional language.
Hopefully, I will be able to get some insights by solving the same problem (sorting numbers) in two different programming paradigms.
Until next time.