Quick sort implementation JavaScript

Question

Im trying to implement quick sort. I wrote partition function which returns array, where first element - number of elements less than pivot and the second - the amount of rest elements.

I ran some tests but i keep getting unlimited recursion. Somehow the array changes only one time and that is it.

I was trying for over a week now :(

const readline = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});

let c, arrSize;
let flagE = false;
let flagG = false;
let flagN = false;

function partition(arr, l, r, pivot){
  let E, G, pointerE, pointerG;
  let N = arr[l];
  while (l <= r){
    if (N > pivot & !flagG){
      G = N;
      pointerG = l;
      flagG = true;
    } else if (N === pivot & !flagE){
      E = N;
      pointerE = l;
      flagE = true;
      if (flagG) {
        arr[l] = G;
        arr[pointerG] = N;
        pointerE = pointerG;
        pointerG++;
      }
    }
     else if (N < pivot & !E & !G){
      flagN = true;
    } 
    else if (N > pivot & flagG) {
      N = arr[l];
    } else if (N < pivot) {
        if (E & G) {
            arr[l] = G;
            arr[pointerG] = E;
            arr[pointerE] = N;
            pointerG++;
            pointerE++;
        } else if (G){
            arr[l] = G;
            arr[pointerG] = N;
            pointerG++;
        } else if (E){
            arr[l] = E;
            arr[pointerE] = N;
            pointerE++;
        }
    }
    l++;
    N = arr[l];
    G = arr[pointerG];
    E = arr[pointerE];
  }

  if (!pointerE & !pointerG & !flagN) {
      return([0, arrSize]);
  } else if (!pointerE & !pointerG & flagN){
      return([arrSize - 1, 0]);
  } else if (pointerE){
      return ([pointerE, r - pointerE]);
  } else if (pointerG & !pointerE) {
      return ([pointerG, arrSize - pointerG]);
  } else {
      return ([pointerG, arrSize - pointerG]);
  }
}

function quickSort(arr, l, r) {
  if (l < r) {
    let x = Math.floor((l + r) / 2);
    let [p, j] = partition(arr, l, r, arr[x]);
    quickSort(arr, l, p);
    quickSort(arr, p + 1, r);
  }
}


readline.on('line', input => {
  let arr;
  if (!c) {
    arrSize = Number(input);
    c = 1;
  } else if (c === 1){
    arr = input.split(' ').map(Number);
    c++;
  }
  if (c === 2){
    quickSort(arr, 0, arrSize - 1);
    console.log(arr.join(' '));
    readline.close()
  }
})

Answer 1

Try this below, may help you to understand the error, where it was failing before.

const readline = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});

let c, arrSize;

function partition(arr, l, r, pivot) {
  let i = l - 1;

  for (let j = l; j < r; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  [arr[i + 1], arr[r]] = [arr[r], arr[i + 1]];
  return i + 1;
}

function quickSort(arr, l, r) {
  if (l < r) {
    let x = Math.floor((l + r) / 2);
    let pivot = arr[x];
    let p = partition(arr, l, r, pivot);
    quickSort(arr, l, p - 1);
    quickSort(arr, p + 1, r);
  }
}

readline.on('line', input => {
  if (!c) {
    arrSize = Number(input);
    c = 1;
  } else if (c === 1) {
    let arr = input.split(' ').map(Number);
    quickSort(arr, 0, arrSize - 1);
    console.log(arr.join(' '));
    readline.close();
  }
});