Skip to content

Instantly share code, notes, and snippets.

@pricees
Last active August 29, 2015 14:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save pricees/76f3fcd17f9db5954148 to your computer and use it in GitHub Desktop.
Save pricees/76f3fcd17f9db5954148 to your computer and use it in GitHub Desktop.
Gnarly quicksort method to be written in Go
$ 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