Sorting algorithms in Ruby, Part 3

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.

Tests

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.

In place

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.

Conclusion

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.

Sorting algorithms in Ruby, Part 1
Sorting algorithms in Ruby, interlude
Sorting algorithms in Ruby, Part 2

2 thoughts on “Sorting algorithms in Ruby, Part 3

  1. Did you happen to complete the functional programming portion of the sorting series? If so could you please point me to where they are located?

    Great series! I really enjoyed all of the posts. I thought they were very well written and very clear.

    Did the out of place QuickSort utilize the Lomuto partition or was the selection of the last element in the array as the starting pivot just a coincidence(Lomuto partition was something mentioned in the Wiki)?

    Thank you,
    Mark

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s