Quicksort for array of objects fails

Question

I couldn't find the answer for this on Stack Overflow.

I have a function called quickSort:

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

    const pivot = array[0]; // I've tried array[0][prop] but it doesn't work
    const left = [];
    const right = [];

    for (let i = 1; i < array.length; i++) {
        if (array[i][prop] < pivot) {
            left.push(array[i]);
        } else {
            right.push(array[i]);
        }
    }

    return [...quickSort(left), pivot, ...quickSort(right)];
}
console.log(quickSort(data, 'motor'));

And I want sort this array of objects by motor:

let data = [
    {
        "color": "A",
        "door": 1,
        "wheel": 3,
        "year": 1963,
        "brand": "GMC",
        "sold": false,
        "owner": "Chalmers Boobyer",
        "motor": 2.6,
        "assembled": "20/08/2021"
    },
    {
        "color": "B",
        "door": 2,
        "wheel": 2,
        "year": 1980,
        "brand": "Ford",
        "sold": false,
        "owner": "Angelia Cromett",
        "motor": 2.5,
        "assembled": "02/05/2021"
    },
    {
        "color": "C",
        "door": 3,
        "wheel": 1,
        "year": 1999,
        "brand": "Audi",
        "sold": false,
        "owner": "Barth Pickring",
        "motor": 2.0,
        "assembled": "15/02/2021"
    },
    {
        "color": "D",
        "door": 4,
        "wheel": 1,
        "year": 2008,
        "brand": "Hyundai",
        "sold": true,
        "owner": "Aurore Soaper",
        "motor": 1.2,
        "assembled": "02/01/2019"
    }
];

Can someone explain how I can make array[0][prop] work?

pivot is an object, so you need to extract property array[i][prop] < pivot[prop] to compare — Yury Tarabanko
– Yury Tarabanko, Commented Dec 27, 2022 at 17:27
When you recursively call quickSort, you are not passing prop. — James
– James, Commented Dec 27, 2022 at 17:28
you are not passing the param prop in this line return [...quickSort(left), pivot, ...quickSort(right)]; — K-Galalem
– K-Galalem, Commented Dec 27, 2022 at 17:29
So like this? return [...quickSort(left, prop), pivot, ...quickSort(right, prop)] — Eduardo S
– Eduardo S, Commented Dec 27, 2022 at 18:24

ggorlen · Accepted Answer · 2022-12-27 19:06:52Z

I suggest reading How to Debug Small Programs. Adding a couple of strategic console.log statements before the comparison and at the start of the function to display the parameters is enough to show the problems. I did it for you this time, but you'll need to be able to debug your own programs if you want to make progress as a programmer.

A couple issues:

Your recursive calls quickSort(left) and quickSort(right) are missing the second parameter prop.
array[i][prop] < pivot is wrong if pivot is defined as array[0] because it compares different types. That should be const pivot = array[0][prop] as you attempted, but then you'd have to change your returned array to be
```
[...quickSort(left, prop), array[0], ...quickSort(right, prop)];
```

Here are the fixes applied:

const quickSort = (array, prop) => {
  if (array.length <= 1) return array;

  // warning: bad pivot
  const pivot = array[0][prop];
  const left = []; // warning: allocations
  const right = [];

  for (let i = 1; i < array.length; i++) {
    if (array[i][prop] < pivot) {
      left.push(array[i]);
    }
    else {
      right.push(array[i]);
    }
  }

  return [
    ...quickSort(left, prop),
    array[0],
    ...quickSort(right, prop)
  ]; // warning: copies
};

const data = [
  {
    color: "A",
    door: 1,
    wheel: 3,
    year: 1963,
    brand: "GMC",
    sold: false,
    owner: "Chalmers Boobyer",
    motor: 2.6,
    assembled: "20/08/2021",
  },
  {
    color: "B",
    door: 2,
    wheel: 2,
    year: 1980,
    brand: "Ford",
    sold: false,
    owner: "Angelia Cromett",
    motor: 2.5,
    assembled: "02/05/2021",
  },
  {
    color: "C",
    door: 3,
    wheel: 1,
    year: 1999,
    brand: "Audi",
    sold: false,
    owner: "Barth Pickring",
    motor: 2.0,
    assembled: "15/02/2021",
  },
  {
    color: "D",
    door: 4,
    wheel: 1,
    year: 2008,
    brand: "Hyundai",
    sold: true,
    owner: "Aurore Soaper",
    motor: 1.2,
    assembled: "02/01/2019",
  },
];

console.log(quickSort(data, "motor"));

After the bug fixes, the sort still has issues:

Recursive sorts shouldn't be allocating memory and copying arrays. Use indices to determine the recursive subarrays and swaps to move elements into the correct subarrays. This makes the code harder to write and read, but provides significant performance improvements.
Choosing the pivot as 0 means you'll hit quadratic complexity and risk blowing the call stack on already-sorted data. Research and choose a better pivot-selection method.
Specifying prop is pretty limited. Better to provide a callback similar to the built-in sort, so you can sort any objects rather than just a top-level prop.

Collectives™ on Stack Overflow

Quicksort for array of objects fails

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related