Home
/
Ruby

Ruby Heapsort

The heapsort is a sorting algorithm that works by first organizing the data to be sorted into a special type of binary tree called a heap. The heap itself has, by definition, the largest value at the top of the tree, so the heap sort algorithm must also reverse the order.

#!/usr/local/bin/ruby

NUM_ITEMS=20

def siftdown(numbers, root, bottom)
   done = 0
   while ((root*2 <= bottom) && (done == 0)) do
      puts "entere while do loop\n"
      if root*2 == bottom 
         maxChild = root * 2
      elsif numbers[root*2] > numbers[root*2+1]
         maxChild = root * 2
      else
         maxChild = root * 2 + 1
      end
      printf("top of if root = %d  maxChild = %d\n",root, maxChild)
      if numbers[root] < numbers[maxChild]
         puts "before swap"
         printf("numbers[root=%d]=%d, numbers[maxChild=%d]=%d\n",root,numbers[root],maxChild,numbers[maxChild])
         puts "swapping root and maxChild\n"
         temp = numbers[root]
         numbers[root] = numbers[maxChild]
         numbers[maxChild] = temp
         puts "after swap"
         printf("numbers[root=%d]=%d, numbers[maxChild=%d]=%d\n",root,numbers[root],maxChild,numbers[maxChild])
         root = maxChild
         printf("bottom if root = %d = maxChild = %d\n",root,maxChild)
      else
         done = 1   # yes done
      end
      for i in 1..NUM_ITEMS do
         printf("numbers[%d] = %d \n",i,numbers[i])
      end
   end
end

def heapSort(numbers)
   bottom = NUM_ITEMS
   for i in 1..bottom do
      printf("numbers[%d]=%d \n",i,numbers[i]) 
   end
   puts "entering count down"
#  i = bottom/2 - 1
   i = bottom/2
   loop do
   #   printf("%d \n", numbers[i])
      siftdown(numbers, i, bottom)
      i -= 1
      break if i < 1
   end
   puts"done making heap, begin sort\n"
   i = NUM_ITEMS 
   loop do
      temp = numbers[1]
      numbers[1] = numbers[i]
      numbers[i] = temp
      i -= 1
      break if i < 1
      siftdown(numbers, 1, i)
   end
end
   
numbers = Array.new
srand(13)
for i in 1..NUM_ITEMS do
   numbers[i] = rand(1000)
end

heapSort(numbers)
puts "Sorted numbers\n"
for i in 1..NUM_ITEMS do
   printf("numbers[%d]=%d \n",i,numbers[i]) 
end

Related Snippets