« back

All Sorts of Things - In Place Quick Sort

26 Oct 2012

In case you missed it last time..... Quicksort via folk dance.

Last time we talked about Quick sort in the context of splitting the sublists up into separate arrays. This time, we are going to work on quicksort "in place", meaning that we will never be breaking the original array out into any other physical named arrays. If you want some background on quicksort or a good discussion on the pivot debate or you don't know what I am talking about, please read my previous post on Quick sort. Let's get started.

Actually, let me back up the truck. Beep Beep..... Let's first talk about the in place quicksort at a higher level. The process usually works like this....

 1        1.Pick your pivot. 
 2             a.This can be done in any fashion you choose but consider your use and do some profiling if necessary.
 3             b.You usually want to move your pivot to be the last element.(in this example to keep it simple, I just picked the last element as the pivot.)
 4        2.Then you do your partitioning.(The breaking up of your list into smaller than the pivot or greater than the pivot.)
 5             a.you start at the left and ask "is this element less than the pivot?  If so keep moving.  If it is greater, stop."
 6             b. then start at the right and ask is this element greater than the pivot?  If so, keep going, if it is less, stop.
 7             c.When both the left and the right have stopped, you swap them. 
 8             d.Repeat until left and right cross each other.
 9             e.Then swap left with the pivot.
10             f.Then recursively sort the left and right parts.
11        

This time we are are going to create a method called in_place_quick_sort. We are still going to pass it an array but in addition to that, we are going to pass it a value for left and a value for right. We will also set a base case for our recursion.

1         def in_place_quick_sort(array, left = 0, right = array.length - 1)
2            return array if right - left < 1
3         end
4     

Now, we want to keep track of where right and left start at each time we pass through, so we will create a left_starting_index and a right_starting_index. Then let's pick the last element as the pivot. To keep track of where the pivot is at, we will also make a pivot_index.

1         def in_place_quick_sort(array, left = 0, right = array.length - 1)
2            return array if right - left < 1
3            left_starting_index = left
4            right_starting_index = right
5            pivot = array[right]
6            pivot_index = right
7         end
8     

Now we want to start that comparison loop where we check for greater and lesser values and swap them.

 1         def in_place_quick_sort(array, left = 0, right = array.length - 1)
 2            return array if right - left < 1
 3            left_starting_index = left
 4            right_starting_index = right
 5            pivot = array[right]
 6            pivot_index = right
 7            loop do
 8              while array[left] < pivot
 9                left += 1
10              end
11              while array[right] >= pivot && right > left
12                right -= 1
13              end
14              if left >= right
15                break
16              elsif left < right
17                array[left], array[right] = array[right], array[left]
18              end
19            end
20          end
21     

Once that loop breaks we want to swap the pivot with the left value. Then we will recursively call in_place_quick_sort for the side to the left of the pivot and then the side to the right of the pivot. Notice that since we will be sorting in place that we always need to pass a left and right value to the method so that it can have the appropriate section to operate on.

 1       def in_place_quick_sort(array, left = 0, right = array.length - 1)
 2            return array if right - left < 1
 3            left_starting_index = left
 4            right_starting_index = right
 5            pivot = array[right]
 6            pivot_index = right
 7            loop do
 8              while array[left] < pivot
 9                left += 1
10              end
11              while array[right] >= pivot && right > left
12                right -= 1
13              end
14              if left >= right
15                break
16              elsif left < right
17                array[left], array[right] = array[right], array[left]
18              end
19            end
20          end
21         array[left], array[pivot_index] = array[pivot_index], array[left]
22         in_place_quick_sort(array, left_starting_index, left - 1)
23         in_place_quick_sort(array, left + 1, right_starting_index)
24        array
25       end
26     

:D Cool.

comments powered by Disqus