Last active
August 29, 2015 14:01
-
-
Save pricees/76f3fcd17f9db5954148 to your computer and use it in GitHub Desktop.
Gnarly quicksort method to be written in Go
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
$ cat qs.rb | |
# | |
# How the merge sort is to be written for a Coursera course I am taking | |
@comps = 0 | |
@stack = 0 | |
def qs(a = [], l = 0, r = nil) | |
#puts "@stack = #{@stack += 1}" | |
pivot = a[l] | |
r ||= a.length | |
#puts "going to work on: #{a[l..r]}" | |
comparisons = (r - l) | |
return if comparisons <= 1 | |
@comps += (comparisons - 1) | |
i = l + 1 # Between less than, greater than pivot | |
(l+1...r).each do |j| | |
if a[j] < pivot | |
a[i], a[j] = a[j], a[i] | |
i += 1 | |
end | |
end | |
a[l], a[i-1] = a[i-1], a[l] | |
p a[l,(i-1-l)] | |
p a[i, a.length - 1] | |
qs a, l, (i-1-l) | |
qs a, i+1, a.length - i | |
end | |
ary = [] | |
#while line = gets | |
# ary << line.to_i | |
#end | |
# | |
ary = 10.times.map { rand(100) } | |
p ary.length | |
qs ary | |
puts "swapping..." | |
puts "total comparisons: #{@comps}" | |
puts "total stack frames: #{@stack}" | |
p ary.first(30), ary.last(30) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment