-
Notifications
You must be signed in to change notification settings - Fork 4
/
quicksort.rb
executable file
·105 lines (85 loc) · 2.53 KB
/
quicksort.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#!/usr/bin/env ruby
def draw( values , colours=Hash.new )
$results ||= begin
at_exit do
puts "NUMBER OF IMAGES: #{$results.size}"
File.open "positions" , "w" do |file|
file.write Marshal.dump($results)
end
end
Array.new
end
$results << colours.merge(:values => values)
end
class QuickSort
def initialize(ary,&block)
block ||= lambda { |a,b| a.send :'<=>' , b }
@values = ary
@compare = block
end
def sort!( left=0 , right=size )
return unless left < right
pivot = left
left.next.upto right-1 do |crnt|
if @compare[ values[pivot] , values[crnt] ] > 0
next_up = values[crnt]
crnt.downto(pivot+1) { |i| values[i] = values[i-1] } # creative liberties ;P
values[pivot] = next_up # older versions had a more strict interpretation, but I felt it was confusing
pivot += 1
end
@pivot = [pivot]
@before_pivot = (0...values.size).to_a.slice left , pivot-left
@after_pivot = (0...values.size).to_a.slice pivot+1 , crnt-pivot
@to_evaluate = (0...values.size).to_a.slice crnt+1 , right-crnt-1
@outside_domain = (0...values.size).to_a - @before_pivot - @after_pivot - @to_evaluate - @pivot
draw
end
sort! left , pivot
sort! pivot+1 , right
values
end
def sort
qs = self.class.new( values.dup , &@compare )
sorted = qs.sort!
qs.send :draw , true
sorted
end
private
def swap( i1 , i2 )
values[i1] , values[i2] = values[i2] , values[i1]
end
def draw( all_green = false )
green = :'#00EE00'
darkred = :'#660000'
darkblue = :'#002C85'
blue = :'#00AEEF'
magenta = :'#F8A1FE'
peach = :'#FF9966'
lavender = :'#CCCCFF'
white = :'#FFFFFF'
if all_green
super values.dup , :colors => { green => values.dup }
else
super values.dup , :colors => { magenta => @after_pivot , blue => @before_pivot , white => @to_evaluate , green => @outside_domain+@pivot }
end
end
def size
values.size
end
attr_reader :values
end
class Array
def bubblesort(&block)
QuickSort.new( self , &block ).sort
end
def bubblesort!(&block)
QuickSort.new( self , &block ).sort!
end
end
unless ARGV.size == 1 && ARGV.first =~ /\A[1-9][0-9]*\Z/
puts "Usage: $ #{$0} [positive quantity of numbers to sort]"
exit 1
end
ary = (0...ARGV.first.to_i).to_a.shuffle
puts "Before sort: #{ary.inspect}"
puts "After sort: #{ary.bubblesort.inspect}"