Class: Array

Inherits:
Object
  • Object
show all
Defined in:
lib/reedb/utils/sorting.rb

Overview

Implements a rather neat and quick heapsort algorithm to sort values for database output.

Instance Method Summary collapse

Instance Method Details

#heapsort ⇒ Object

Heapsorts a douplicate instance and leaves the original alone.



16
17
18
 
# File 'lib/reedb/utils/sorting.rb', line 16

def heapsort
	self.dup.heapsort!
end

#heapsort! ⇒ Object

Heapsorts that array instance.



22
23
24
25
26
27
28
29
30
31
 
# File 'lib/reedb/utils/sorting.rb', line 22

def heapsort!
	# Heapify the array!
	((length - 2) / 2).downto(0) {|first| siftdown(first, length - 1)}

	(length - 1).downto(1) do |last|
		self[last], self[0] = self[0], self[last]
		siftdown(0, last - 1)
	end
	self
end

#siftdown(first, last) ⇒ Object 



33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
# File 'lib/reedb/utils/sorting.rb', line 33

def siftdown(first, last)
	root = first
	loop do
		child = root * 2 + 1
		break if child > last
		if child + 1 <= last and self[child] < self[child + 1]
			child += 1
		end
		if self[root] < self[child]
			self[root], self[child] = self[child], self[root]
			root = child
		else
			break
		end
	end
end