Sorts an array of numbers, using the heapsort algorithm.
- Use recursion.
- Use the spread operator (
...
) to clone the original array,arr
. - Use closures to declare a variable,
l
, and a functionheapify
. - Use a
for
loop andMath.floor()
in combination withheapify
to create a max heap from the array. - Use a
for
loop to repeatedly narrow down the considered range, usingheapify
and swapping values as necessary in order to sort the cloned array.
const heapsort = arr => { const a = [...arr]; let l = a.length; const heapify = (a, i) => { const left = 2 * i + 1; const right = 2 * i + 2; let max = i; if (left < l && a[left] > a[max]) max = left; if (right < l && a[right] > a[max]) max = right; if (max !== i) { [a[max], a[i]] = [a[i], a[max]]; heapify(a, max); } }; for (let i = Math.floor(l / 2); i >= 0; i -= 1) heapify(a, i); for (i = a.length - 1; i > 0; i--) { [a[0], a[i]] = [a[i], a[0]]; l--; heapify(a, 0); } return a; };
Examples
heapsort([6, 3, 4, 1]); // [1, 3, 4, 6]
Recommended snippets
Sorts an array of numbers, using the quicksort algorithm.
Sorts an array of numbers, using the merge sort algorithm.
Sorts an array of numbers, using the bucket sort algorithm.