Help with Quick Sort code [Solved]

Help with Quick Sort code [Solved]
0

#1

I am trying to write a primitive quick sort code, with the pivot element in each recursion call being the first element of the array. I have completed my code and the recursion calls and partitions are correct but the final output is always the array obtained after the first partition call. Any idea what’s causing this problem?

function partition(arr, l, r) {
  var p, i, j, swap = 0;
  p = arr[l];
  i = l + 1;
  for (j = 1; j < arr.length; j++) {
    if (arr[j] < p) {
      swap = arr[i];
      arr[i] = arr[j];
      arr[j] = swap;
      i ++;
    }
  } 
  swap = arr[l];
  arr[l] = arr[i - 1];
  arr[i - 1] = swap;
  return i - 1; 
}

function quickSort(arr, n) {
  var q, left, right;
  if (arr.length > 1) {
    q = partition(arr, 0, arr.length - 1);
    console.log(q, arr[q]);
    left = arr.slice(0, q);
    right = arr.slice(q + 1, arr.length);
    console.log(left, right);
    quickSort(left, left.length);
    quickSort(right, right.length);
  }
}

array = [6, 4, 2, 3, 5, 7, 9, 8, 1];
quickSort(array, array.length);
console.log(array);

Thank you.


#2

Nevermind, figured it out. I made the mistake of passing smaller array sections to the recursive calls rather than recursing on smaller parts of the same array. As quick sort has no merge step my input array was sorted correctly at the base level, but this sorted parts were never stitched together to give the sorted output array. In the modified code I have made recursive calls on smaller sections of the same array using indexes as parameters.
Hope this helps someone stuck on the same problem in the future. Leaving the code down below for future reference.

function partition(arr, l, r) {
  var i, j, swap = 0, p;
  p = arr[l];
  i = l + 1;
  for (j = l + 1; j <= r; j++) {
    if (arr[j] < p) {
      swap = arr[i];
      arr[i] = arr[j];
      arr[j] = swap;
      i++;
    }
  }
  swap = arr[l];
  arr[l] = arr[i - 1];
  arr[i - 1] = swap;
  return i - 1;
}

function quickSort(arr, l, r) {
  var index;
  if (arr.length > 1) {
    index = partition(arr, l, r);
    if (l < index - 1) {
      quickSort(arr, l, index - 1);
    }
    if (r > index) {
      quickSort(arr, index + 1, r);
    }
  }
}

//array = [6, 4, 2, 3, 5, 7, 9, 8, 1];
var array = [2, 1, 5, 6, 4, 64, 2, 1, 3, 1, 65, 8, 7, 41, 1, 3, 23, 6, 57, 5, 64, 12, 301, 24, 65];
quickSort(array, 0, array.length - 1);
console.log(array);