Algorithm Implementation/Sorting/Introsort
Appearance
Ruby
[edit | edit source]Ruby implementation with simple test
#!/usr/bin/env ruby
#
# Introsort is a version of Quicksort with "introspection".
#
# When Introsort notices that its recursion depth exceeds
# a specified height, it switches over to Heapsort to
# process the (Quicksort) partition it is currently working on.
# In this way the recursion depth does not continue to increase
# as it would with Quicksort. Unconstrained recursion can reduce
# Quicksort's performance to O(n^2), whereas on the same data,
# Introsort guarantees a worst-case performance of O(n*log2(n)).
#
# This version of Introsort switches to Heapsort when its
# recursion depth reaches 2*(floor(log2(n))).
# See Musser, David (1997). "Introspective Sorting and Selection Algorithms".
# Software: Practice and Experience 27 (8): 983?993. Wiley.
#
# The algorithm for Heapsort is adapted from
# Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001).
# Introduction to Algorithms, second edition, MIT Press and McGraw-Hill.
#
class Heapsort
def initialize(ary)
@ary = ary.dup
@heap_size = ary.length
end
def heapsort
build_max_heap
@ary.length.downto(2) {|i|
swap(1, i)
@heap_size -= 1
max_heapify(1)
}
@ary
end
def build_max_heap
parent(@heap_size).downto(1) {|i|
max_heapify(i)
}
end
def max_heapify(i)
l = left(i)
r = right(i)
largest = (l <= @heap_size and @ary[l-1] > @ary[i-1]) ? l : i
largest = r if (r <= @heap_size and @ary[r-1] > @ary[largest-1])
if largest != i
swap(i, largest)
max_heapify(largest)
end
end
def parent(i)
(i / 2).floor
end
def left(i)
2 * i
end
def right(i)
(2 * i) + 1
end
def swap(i, j)
@ary[i-1], @ary[j-1] = @ary[j-1], @ary[i-1]
end
end
def introloop(ary, depth_limit)
return ary if ary.size <= 1
return Heapsort.new(ary).heapsort() if depth_limit == 0
depth_limit -= 1
pivot = ary.pop
left, right = ary.partition { |e| e < pivot }
introloop(left, depth_limit) + [pivot] + introloop(right, depth_limit)
end
def introsort(ary)
introloop(ary, 2 * (Math.log10(ary.size) / Math.log10(2)).floor)
end
if $0 == __FILE__
print introsort([1, 4, 7, 2, 1, 3, 2, 1, 4, 2, 3, 2, 1]).join(", ") + "\n"
# prints: 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 7 without calling heapsort
print introsort([13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]).join(", ") + "\n"
# prints: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
# and calls heapsort once for subarray [13, 12, 11, 10, 9, 8, 7]
end