Implementation of a counter of comparisons for the quickSort algorithm in javascript

Question

I'm trying to implement a counter of comparisons for the quickSort algorithm in javascript.

I have tested my code agains't some base cases, and my result is always very close to the correct one (22 instead of 25 for this test). I can't figure out what's wrong with my code, any help would be appreciated.

Thank you.

let comparisons = 0;


    function quick_Sort(origArray) {
        if (origArray.length <= 1) { 
            return origArray;
        } else {

            var left = [];
            var right = [];
            var newArray = [];
            var pivot = origArray.shift();
            var length = origArray.length;
            // I have tried comparisons += length - 1; too, but i doesn't work
            comparisons += length;
            for (var i = 0; i < length; i++) {
                if (origArray[i] <= pivot) {
                    left.push(origArray[i]);
                    
                } else {
                    right.push(origArray[i]);
                }
            }
    
            return newArray.concat(quick_Sort(left), pivot, quick_Sort(right));
        }
    }

quick_Sort([2148, 9058, 7742, 3153, 6324, 609, 7628, 5469, 7017, 504]); 
// expected output: 25

console.log(comparisons);

Answer 1

You must change comparaisons += length - 1; with comparaisons += length;. The number of comparisons are equal to the number of iterations of the for loop.

This is a trace of the complete process with the sample array that you have provided, showing the number of comparisons, the pivot, left and right parts of each recursion step. The number of comparisons is not 25, it is equal to 29:

[ 2148, 9058, 7742, 3153, 6324, 609, 7628, 5469, 7017, 504 ] (Comparisons: 9)
- Pivot: 2148
- Left: [ 609, 504 ] (Comparisons 1)
- Right: [ 9058, 7742, 3153, 6324, 7628, 5469, 7017 ] (Comparisons: 6)
  - Pivot: 9058
  - Left: [ 7742, 3153, 6324, 7628, 5469, 7017 ] (Comparisons: 5)
    - Pivot: 7742
    - Left: [ 3153, 6324, 7628, 5469, 7017 ] (Comparisons: 4)
      - Pivot: 3153
      - Left: [ ]
      - Right: [ 6324, 7628, 5469, 7017 ] (Comparisons: 3)
        - Pivot: 6354
        - Left: [ 5469 ]
        - Right: [ 7628, 7017 ] (Comparisons: 1)
    - Right: [ ]
  - Right: [ ]