Implementing Heapsort Algorithm in JavaScript

Introduction

In this lab, we will explore the implementation of the heapsort algorithm in JavaScript. Heapsort is a comparison-based sorting algorithm that works by dividing an array into a sorted and an unsorted region, and iteratively shrinking the unsorted region by extracting the largest element and moving that to the sorted region. Through this lab, you will gain a deeper understanding of how the heapsort algorithm works and how to implement it using recursion and closures in JavaScript.

Heap Sort Algorithm

To practice coding, open the Terminal/SSH and type 'node'. The following algorithm sorts an array of numbers using the heapsort algorithm. Follow these steps:

• Use recursion in the function.
• Use the spread operator (...) to clone the original array, arr.
• Use closures to declare a variable, l, and a function heapify.
• Use a for loop and Math.floor() in combination with heapify to create a max heap from the array.
• Use a for loop to repeatedly narrow down the considered range, using heapify and swapping values as necessary 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 (let i = a.length - 1; i > 0; i--) {
    [a[0], a[i]] = [a[i], a[0]];
    l--;
    heapify(a, 0);
  }
  return a;
};

For example:

heapsort([6, 3, 4, 1]); // [1, 3, 4, 6]

Summary

Congratulations! You have completed the Heap Sort lab. You can practice more labs in LabEx to improve your skills.