Support with 'Quick Sort' Algorithm

user_15347233 0
Viewed 56

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]);
quicksort recursion sorting algorithm javascript
3 Answers

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]);

user_81306900

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

user_114510

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.

user_149896300
Related