skip to Main Content

I’m currently learning some sorting algorithms and I made my realisation of quick sort, but it didn’t work properly. Instead of just sorting the array, it deleted duplicate values. Here is my code:

function quickSort(array) {
    if (array.length <= 1) return array;

    let pivotIndex = Math.floor(array.length / 2);
    let pivot = array[pivotIndex];
    let less = [];
    let greater = [];

    for (let i = 0; i < array.length; i++) {
        count++;
        if (i === pivotIndex) continue;
        if (array[i] < pivot) { // *
            less.push(array[i]);
        } 
        if (array[i] > pivot) {
            greater.push(array[i])
        }
        
    }

    return [...quickSort(less), pivot, ...quickSort(greater)];
}

When I replaced two if’s (starting from line *) to the following code, it started working:

if (array[i] < pivot) {
   less.push(array[i]);
} else {
   greater.push(array[i])
}

I just don’t understand what the difference and why the first variant isn’t working?
And also why it works longer than selection sort or sometimes even bubble sort?

I also tried adding "continue" in the end of each if, but it doesn’t help.

3

Answers


  1. Replace:

        if (array[i] < pivot) { // *
            less.push(array[i]);
        } 
        if (array[i] > pivot) {
            greater.push(array[i])
        }
    

    With:

        if (array[i] < pivot) { // *
            less.push(array[i]);
        } else {
            greater.push(array[i])
        }
    
    Login or Signup to reply.
  2. if (array[i] < pivot) { // *
      less.push(array[i]);
    } 
    if (array[i] > pivot) {
      greater.push(array[i])
    }
    

    In this option you miss values array[i] === pivot. Thus deleting them.

    Login or Signup to reply.
  3. Note that if array[i] > pivot, code (1) will do nothing but (2) will push array[i] to greater. So it will behave differently when there are duplicate values in array.

    Login or Signup to reply.
Please signup or login to give your own answer.
Back To Top
Search