Quicksort for array of objects fails-CodePudding

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?

CodePudding user response：

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.