JavaScript quickSort wrong output

Question

This is the quicksort algorithm I wrote:

var arr = [0, 2, 5, 10, 3, 22, 12, 8, 20];

let quickSort = (arr) => {
  let len = arr.length;

  if (len === 1) {
    return arr;
  };

  let pivot = arr.length - 1;

  const rightArr = [];
  const leftArr = [];

  for (let i = 0; i < len - 1; i++) {
    let j = i + 1;
    if (arr[j] > arr[pivot]) {
      rightArr.push(arr[j]);
    } else {
      leftArr.push(arr[j]);
    };
  };
  if (leftArr.length > 0 && rightArr.length > 0) {
    return [...quickSort(leftArr), pivot, ...quickSort(rightArr)];
  } else if (leftArr.length > 0 && rightArr.length <= 0) {
    return [...quickSort(leftArr), pivot];
  } else {
    return [pivot, ...quickSort(rightArr)];
  };
};

console.log(quickSort(arr));

The output is: [20, 1, 2, 3, 4, 5, 6, 8, 22]

My question is: why do I get the wrong output and how do I fix this ?

fwiw, quicksort is supposed to sort an array in place. The posted function creates new sub-arrays by copying into new arrays, which real quicksort does not do. — Pointy
– Pointy, Commented Jul 25, 2021 at 12:16
There is much wrong with this code, but the problem arises from adding pivot to the list instead of arr[pivot], pivot being the index — Vulwsztyn
– Vulwsztyn, Commented Jul 25, 2021 at 12:20
thank you @Vulwsztyn i solved the problem and evreything work just fine. — Rabie Ouallaf
– Rabie Ouallaf, Commented Jul 25, 2021 at 12:28
Since I apparently resolved your issue I added my comment as answer. Would you mind accepting it? — Vulwsztyn
– Vulwsztyn, Commented Jul 25, 2021 at 12:46

Vulwsztyn · Accepted Answer · 2021-07-25 12:46:17Z

2

There is much wrong with this code, but the problem arises from adding pivot to the list instead of arr[pivot], pivot being the index

answered Jul 25, 2021 at 12:46

Vulwsztyn

2,2711 gold badge15 silver badges23 bronze badges

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

1 Comment

Vulwsztyn Over a year ago

e.g.: all conditions at the end of code are redundant, why would you use semicolon in js? it's not real in-situ quicksort, for that you should be swaping elements of the array and not create additional ones

Collectives™ on Stack Overflow

JavaScript quickSort wrong output

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related