JavaScript, HeapSort - count swaps and comparisons

Question

How i should count swaps and comparisons? I'm new in programmin and algorithms. So, I got a problem to count swaps and comparisons, the problem is that i don't know how to save the value of counters in recursive function There is code explanation https://levelup.gitconnected.com/heapsort-for-javascript-newbies-598d25477d55

function heapify(arr, length, i) {
    let largest = i
    let left = i * 2 + 1
    let right = left + 1

    if (left < length) {
        if(arr[left] > arr[largest]) {
            largest = left
        }
    }

    if (right < length) {
        if(arr[right] > arr[largest]) {
            largest = right
        }
    }

    if(largest != i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]]
        heapify(arr, length, i)
    }
    return arr
}

function heapSort(arr) {
    let length = arr.length
    let i = Math.floor(length / 2 - 1)
    let k = length - 1
    
    while (i >= 0) {
        heapify(arr, length, i)
        i--
    }

    while (k >= 0) {
        [arr[0], arr[k]] = [arr[k], arr[0]]
        heapify(arr, k, 0)
        k--
    }

    return arr
}

Answer 1

Since it is an inplace sorting algorithm, you don't really have to return the array. The caller already has passed the array, so they don't really need the same array reference again. You can then instead use the return value for the number of swaps.

Side note: there is a bug in your heapify function: the recursive call should get largest as last argument instead of i. I have corrected that below as well:

function heapify(arr, length, i) {
    let largest = i;
    let left = i * 2 + 1;
    let right = left + 1;

    if (left < length) {
        if(arr[left] > arr[largest]) {
            largest = left;
        }
    }

    if (right < length) {
        if(arr[right] > arr[largest]) {
            largest = right;
        }
    }

    if(largest != i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        // count the above swap, and those made by the recursive calls
        return 1 + heapify(arr, length, largest);
    }
    return 0; // Nothing was swapped here
}

function heapSort(arr) {
    let length = arr.length;
    let i = Math.floor(length / 2 - 1);
    let k = length - 1;
    
    let swapCount = 0; // running sum
    while (i >= 0) {
        swapCount += heapify(arr, length, i);
        i--
    }

    while (k >= 0) {
        [arr[0], arr[k]] = [arr[k], arr[0]];
        // Count the above swap and those made by heapify:
        swapCount += 1 + heapify(arr, k, 0);
        k--;
    }
    
    return swapCount;
}
let arr = [4, 2, 9, 7, 1, 3, 8, 0, 5, 6];
let swapCount = heapSort(arr);
console.log("sorted:", ...arr);
console.log("swaps:", swapCount);

If you want to both count the comparisons and the swaps, then you would need to return an object/array with this pair. In that case it may be easier to pass that object as optional argument to heapify, which will then adjust the counts in that object:

function heapify(arr, length, i, counter = { comparisons: 0, swaps: 0 }) {
    let largest = i;
    let left = i * 2 + 1;
    let right = left + 1;

    if (left < length) {
        counter.comparisons++; // For the next `if` condition
        if(arr[left] > arr[largest]) {
            largest = left;
        }
    }

    if (right < length) {
        counter.comparisons++; // For the next `if` condition
        if(arr[right] > arr[largest]) {
            largest = right;
        }
    }

    if(largest != i) {
        counter.swaps++;
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, length, largest, counter);
    }
}

function heapSort(arr) {
    let length = arr.length;
    let i = Math.floor(length / 2 - 1);
    let k = length - 1;
    
    let counter = {
        comparisons: 0, // running sum
        swaps: 0 // running sum
    }
    while (i >= 0) {
        heapify(arr, length, i, counter);
        i--;
    }

    while (k >= 0) {
        counter.swaps++;
        [arr[0], arr[k]] = [arr[k], arr[0]];
        heapify(arr, k, 0, counter);
        k--;
    }
    
    return counter;
}
let arr = [4, 2, 9, 7, 1, 3, 8, 0, 5, 6];
let counter = heapSort(arr);
console.log("sorted:", ...arr);
console.log("counters:", counter);