Support with 'Quick Sort' Algorithm

Question

I am having problems with my quick-sort algorithm implementation that uses recursion. When I use the function on an array with duplicate numbers, it ignores those numbers in the final result and I don't know why. Anyone know what I did wrong? (JavaScript)

function getRandomInt(max) {
  return Math.floor(Math.random() * Math.floor(max));
}

let quickSort = (arr) => {
    if (arr.length <= 1) return arr;
    
    const pivot = arr[getRandomInt(arr.length)]
    let smallerArr = [];
    let greaterArr = [];
    
    for (let item of arr) {
        if (item !== pivot) {
            if (item > pivot) {
                greaterArr.push(item);
                continue
            }
            smallerArr.push(item);
        }
        
    }
    let sorted = quickSort(smallerArr);
    sorted = sorted.concat([pivot],quickSort(greaterArr));
    console.log(sorted);
    return sorted;
}
quickSort([5,7,6,23,6]);

Lakshya Thakur · Accepted Answer · 2021-03-07 13:14:27Z

3

You only want to skip the element whose pivotIndex matches with the current index. I switched back to the for(let i = 0,index......) approach to keep track of the same. What you're currently doing is skipping all the items whose value matches with the pivot which means duplicates are also removed from being considered if the pivot element has duplicates in the array.

function getRandomInt(max) {
  return Math.floor(Math.random() * Math.floor(max));
}

let quickSort = (arr) => {
    if (arr.length <= 1) return arr;
    
    const pivotIndex = getRandomInt(arr.length);
    const pivot = arr[pivotIndex];
    let smallerArr = [];
    let greaterArr = [];
    for(let index = 0;index<arr.length;index++)
    {
            if(index===pivotIndex)
               continue;
            const item = arr[index];   
            if (item > pivot) 
            greaterArr.push(item);
            else 
            smallerArr.push(item);
    }
    let sorted = quickSort(smallerArr);
    sorted = sorted.concat(pivot,quickSort(greaterArr));
    console.log(sorted);
    return sorted;
}
quickSort([5,7,6,23,6,6,6,6]);

edited Mar 7, 2021 at 13:14

answered Mar 7, 2021 at 13:07

Lakshya Thakur

8,3141 gold badge15 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

JakubGamer Over a year ago

Thanks so much! I must have overlooked that bug. Have a nice day!

Kristof Neirynck · Accepted Answer · 2021-03-07 10:51:07Z

0

What happens when item !== pivot is false? You seem to skip that item.

answered Mar 7, 2021 at 10:51

Kristof Neirynck

4,2132 gold badges38 silver badges52 bronze badges

1 Comment

JakubGamer Over a year ago

See the response to the person above ^

Viviane Costa · Accepted Answer · 2021-03-07 12:53:54Z

0

You need to make clear what your code should do when item === pivot. Right now your code is only ignoring those values because it is not inserting on either greaterArr and smallerArr. Add an else statement to fix this.

answered Mar 7, 2021 at 12:53

Viviane Costa

392 bronze badges

Collectives™ on Stack Overflow

Support with 'Quick Sort' Algorithm

3 Answers 3

1 Comment

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related