Trying to convert my Quicksort function such that it can process array of objects and sort by the value inside the object

Question

I am currently trying to tinker my Quicksort function so I can test the real life issue when there is array of object that has same sort target, yet different ID.

Below are my two different codes where pivot selection mechanisms are different to each other.

//first Code


function quickSort(array) {
  if (array.length === 1) return array; // base case
  let pivot = array[array.length - 1]; 
  let leftArr = [];
  let rightArr = [];

  for(let el of array) {
      if (el.num < pivot.num) {
          leftArr.push(el); 
      } else {
          rightArr.push(el); 
      }
  }
  console.log(rightArr);
  console.log(leftArr);

  if (leftArr.length > 0 && rightArr.length > 0) {
    return [...quickSort(leftArr), pivot, ...quickSort(rightArr)] 
  } else if (leftArr.length > 0) {
    return [...quickSort(leftArr), pivot]
  } else {
    return [pivot, ...quickSort(rightArr)] 
  }
}

// second Code 

function quickSort2(arr) {
  if (!arr.length) {
    return arr;
  }
  let pivotIdx = Math.floor(Math.random() * (arr.length));
  let pivot = arr[pivotIdx];
  let head = [];
  let tail = [];
  let exceptPivot = arr.slice(0, pivotIdx).concat(arr.slice(pivotIdx + 1));
  for (let el of exceptPivot) {
    if (el.num <= pivot.num) {
      head.push(el)
    } else {
      tail.push(el)
    }
  }
  // return quickSort1(head).concat([pivot].concat(quickSort1(tail)));
  return [...quickSort1(head), pivot, ...quickSort1(tail)];
};

And below is the test:

let test = [
  {id: 4, num: 21},
  {id: 7, num: 22},
  {id: 12, num: 24},
  {id: 5, num: 100},
  {id: 6, num: 100},
  {id: 32, num: 14},
  {id: 19, num: 15},
  {id: 23, num: 16},
  {id: 1, num: 15},
  {id: 42, num: 100},
  {id: 56, num: 100},
  {id: 74, num: 100}
]

For the first code, I am getting lots of stacks as results. And ends up not sorting at all. For the second code, I am getting array results only.

Would you please point out the logics that I didn't consider and glitch in my codes? Thank you in advance.

Answer 1

For the first code, your code produces infinite-loop because you did not consider what would happen when el.num === pivot.num. For example,

array = [
  {id: 4, num: 21},
  {id: 7, num: 22},
  {id: 12, num: 24},
  {id: 19, num: 15},
  {id: 23, num: 16},
  {id: 1, num: 15}
]

would go to this else-logic forever.

else {
    return [pivot, ...quickSort(rightArr)] 
}

Now, the solution is simple, check when num key of 2-elements are equal. For example:

function quickSort(array) {
  if (array.length <= 1) return array; // note that array.length === 0 is also base case
  
  let pivot = array[array.length - 1]; 
  let leftArr = [];
  let rightArr = [];
  let sameArr = []; // to save elements with same num value
  for(let el of array) {
      if (el.num < pivot.num) {
          leftArr.push(el); 
      } else if(el.num > pivot.num) {
          rightArr.push(el); 
      } else {
          sameArr.push(el);
      }
  }

  return [...quickSort(leftArr), ...sameArr, ...quickSort(rightArr)]
}

But what happen when 2 elements have the same num-value but different id-value? That depends on your use-case, which one has higher priority? num or id?

If you want to sort based on id-value first, then num-value second:

function quickSort(array) {
  if (array.length <= 1) return array; // base case
  
  let pivot = array[array.length - 1]; 
  let leftArr = [];
  let rightArr = [];
  let sameArr = [];
  for(let el of array) {
      if (el.id < pivot.id) {
          leftArr.push(el); 
      } else if(el.id > pivot.id) {
          rightArr.push(el); 
      } else {
        if (el.num < pivot.num) {
          leftArr.push(el);
        } else if (el.num > pivot.num) {
          rightArr.push(el);
        } else {
          sameArr.push(el);
        }
      }
  }

  return [...quickSort(leftArr), ...sameArr, ...quickSort(rightArr)]
}

If you want to sort based on num-value first, then id-value second:

function quickSort(array) {
  if (array.length <= 1) return array; // base case
  
  let pivot = array[array.length - 1]; 
  let leftArr = [];
  let rightArr = [];
  let sameArr = [];
  for(let el of array) {
      if (el.num < pivot.num) {
          leftArr.push(el); 
      } else if(el.num > pivot.num) {
          rightArr.push(el); 
      } else {
        if (el.id < pivot.id) {
          leftArr.push(el);
        } else if (el.id > pivot.id) {
          rightArr.push(el);
        } else {
          sameArr.push(el);
        }
      }
  }

  return [...quickSort(leftArr), ...sameArr, ...quickSort(rightArr)]
}

When there are a lot of object keys to compare, you can further simplify this by making an additional array of priority and compare the elements in-order of it's key's priority level.