Algorithms - Implement Quick Sort

Tell us what’s happening:
Describe your issue in detail here.

Your code so far
This code working on small data set like [2,6,5,3,8,7,1,0] but unable to sort on large data set like in example provided. I know there is something wrong with the logic but I am unable to figure it out using “Python Tutor code visualizer” , there are so many return on the stack and I am losing the count and not able to write it on paper as well.
Please provide a solution to manage such kind of problem in real life.
Thanks,

function pivot(arr,left=0, right=arr.length-1) {
  
let ind = Math.floor((right-left)/2)+left;
let p = arr[ind];
let i=left;
let j=right;
swap(arr,ind,right);
j=j-1;
while (i<=j){
  if(arr[i]>p && arr[j]<p){
    swap(arr,i,j);
  }
  else if(arr[i]>p && arr[j]>p){
    j--;
  }
  else if(arr[i]<p && arr[j]<p){
    i++;
  }
  else{
    i++;
    j--;
  }
}
arr[right]=arr[i];
arr[i]=p;
return i;
}

function swap(arr,a,b){
  let temp = arr[a];
  arr[a]=arr[b];
  arr[b]=temp;
}

function quickSort(array, left = 0, right = array.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(array, left, right);
    quickSort(array, left, pivotIndex - 1);
    quickSort(array, pivotIndex + 1, right);
  }
  return array;
}
console.log(quickSort([1,4,2,8,345,123,43,32,5643,63,123,43,2,55,1,234,92]));

Your browser information:

User Agent is: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/114.0.0.0 Safari/537.36

Challenge: Algorithms - Implement Quick Sort

Link to the challenge:

It appears there’s an issue with the numbers that occur multiple times in the array. A simpler test case:

console.log(quickSort([1, 20, 1, 20, 1]))

Thanks Sanity, your test case helped me to sloved the problem.
Can you please suggest, how to debug such problem…

Looking for simpler test cases is a great strategy

1 Like

I was printing the array, with couple other variables like left, right, or p, after each full pivot and noticed, at some point one number was ending up on the wrong side of pivot value. After some more tinkering with the code, I didn’t find where exactly error is in code, but it occurred to me the troublesome numbers were the ones appearing more than once in array.

1 Like

Thanks Sanity for details explanation, I will try to use your approch in my coding practice.
I like your name, it gives lot of positive vibes…

1 Like

Thanks Jeremy for always looking into my issues and your valuable comments.

1 Like

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.