Created
October 15, 2014 04:04
-
-
Save ambirdsall/4499b0d4f67e0aff7c09 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # for reference: http://www.youtube.com/watch?v=3OLTJlwyIqQ | |
| require 'pp' | |
| def quicksort(arr, from=0, to=nil) | |
| to = arr.length-1 if to.nil? | |
| # exit condition for recursion | |
| return if to - from < 1 | |
| pivot_location = move_pivot_to_sorted_location(arr, from, to) | |
| # once every value less than the pivot has been shifted left of it and | |
| # every value greater that in has been shifted right of it, the pivot is | |
| # in its final position. Call quicksort on the subarrays left and right | |
| # of the pivot, unless they're the right- or left-most element of the | |
| # (sub)array in question. | |
| quicksort(arr, from, pivot_location-1) unless pivot_location == from | |
| quicksort(arr, pivot_location+1, to) unless pivot_location == to | |
| end | |
| def move_pivot_to_sorted_location(arr, left, right) | |
| pivot = left | |
| until left == right | |
| if pivot == left | |
| pivot, left, right = compare_pivot_to_right(arr, pivot, right) | |
| elsif pivot == right | |
| pivot, left, right = compare_pivot_to_left(arr, pivot, left) | |
| end | |
| end | |
| pivot | |
| end | |
| def compare_pivot_to_right(arr, pivot, right) | |
| if arr[pivot] > arr[right] | |
| # swap values at pivot and right | |
| temp = arr[right] | |
| arr[right] = arr[pivot] | |
| arr[pivot] = temp | |
| # and return updated locations of left, right, and pivot for next iteration | |
| return [right, pivot + 1, right] | |
| end | |
| # if no swap is needed, move right in one for next iteration | |
| [pivot, pivot, right - 1] | |
| end | |
| def compare_pivot_to_left(arr, pivot, left) | |
| # logically identical to the above, except direction changed to reflect a | |
| # post-swap world. At least the part of the world being quicksorted. | |
| if arr[pivot] < arr[left] | |
| temp = arr[left] | |
| arr[left] = arr[pivot] | |
| arr[pivot] = temp | |
| return [left, left, pivot - 1] | |
| end | |
| [pivot, left + 1, pivot] | |
| end | |
| test = [] | |
| 15.times do | |
| test << rand(40) | |
| end | |
| pp "UNSORTED ARRAY: #{test}" | |
| quicksort test | |
| pp "SORTED ARRAY: #{test}" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment