Heap Sort

Sort an array using the heap sort algorithm with O(n log n) time complexity.

Code

Algorithms

def heapify(a, n, i)
  largest, l, r = i, 2 * i + 1, 2 * i + 2
  largest = l if l < n && a[l] > a[largest]
  largest = r if r < n && a[r] > a[largest]
  if largest != i
    a[i], a[largest] = a[largest], a[i]
    heapify(a, n, largest)
  end
end

a = arr.dup
n = a.length
(n / 2 - 1).downto(0) { |i| heapify(a, n, i) }
(n - 1).downto(1) do |i|
  a[0], a[i] = a[i], a[0]
  heapify(a, i, 0)
end
a

Parameters

arr(array)

Array to sort

Server

More Ruby Snippets

Bubble Sort

Sort an array using the bubble sort algorithm by repeatedly swapping adjacent elements.

Counting Sort

Sort an array of non-negative integers using counting sort for linear time performance.

Insertion Sort

Sort an array using the insertion sort algorithm by building a sorted portion one element at a time.

Merge Sort

Sort an array using the merge sort algorithm with O(n log n) time complexity.

Quicksort

Sort an array using the quicksort algorithm with average O(n log n) time complexity.

Selection Sort

Sort an array using the selection sort algorithm by repeatedly finding the minimum element.