Блог

В настоящее время я пытаюсь доработать свою функцию быстрой сортировки, чтобы я мог проверить реальную проблему, когда есть массив объектов, который имеет ту же цель сортировки, но другой идентификатор.

Ниже приведены мои два разных кода, в которых механизмы сводного выбора отличаются друг от друга.

 //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 amp;amp; 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)];
};

  

И ниже приведен тест:

 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}
]
  

Для первого кода я получаю много стеков в качестве результатов. И в итоге вообще не сортирует.
Для второго кода я получаю только результаты массива.

Не могли бы вы указать на логику, которую я не учел, и сбой в моих кодах? Заранее благодарю вас.

Для первого кода ваш код создает бесконечный цикл, потому что вы не учли, что произойдет, когда el.num === pivot.num. Например,

 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}
]
  

переход к этой другой логике навсегда.

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

Теперь решение простое, проверьте, когда числовой ключ из 2 элементов равен. Например:

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

Но что произойдет, когда 2 элемента имеют одинаковое значение num, но разное значение id?
Это зависит от вашего варианта использования, который имеет более высокий приоритет? число или идентификатор?

Если вы хотите сначала выполнить сортировку на основе значения id, затем значения num:

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

Если вы хотите сначала выполнить сортировку на основе значения num, затем значения id:

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

Когда есть много ключей объекта для сравнения, вы можете еще больше упростить это, создав дополнительный массив приоритетов и сравнив элементы в порядке уровня приоритета этого ключа.