быстрая сортировка избавляет от повторяющихся значений - PullRequest
Новая
       5

быстрая сортировка избавляет от повторяющихся значений

1 голос
/ 24 января 2020

Я попытался написать некоторый код для запуска быстрой сортировки в javascript, но окончательный массив возвращается без дубликатов (если они изначально были) 

function quickSort(array) {
  if (array.length <= 1) return array;
  var pivot = array[0];

var left = quickSort(array.filter(item =>item < pivot));
var right = quickSort(array.filter(item =>item > pivot));

//console.log('left ',left);
//console.log("right ",right);

  return [...left,pivot,...right];
}

console.log(quickSort([5, 4, 3, 2, 1, 1, 2])); // <- this returns [1,2,3,4,5]

1 Ответ

2 голосов
/ 24 января 2020

Проблема в том, что вы фильтруете, оставляя только те элементы, которые строго ниже (<) или строго выше (>), чем ваш пивот.

Это можно исправить, изменив одно из следующих значений: ваши условия <= вместо < (или >= вместо >). Обратите внимание, что когда вы делаете это, вы должны убедиться, что элемент pivot вынут из массива.

Итак, в этой строке: 

var left = quickSort(array.filter(item =>item < pivot));

Мы можем вывести pivot, вызвав array.slice(1) (обратите внимание, что это не очень эффективно, см. Модифицированное решение в конце). Затем мы изменяем условие на <=, и окончательный код становится следующим: 

function quickSort(array) {
  if (array.length <= 1) return array;
  var pivot = array[0];

  var left = quickSort(array.slice(1).filter(item =>item <= pivot));
  var right = quickSort(array.filter(item =>item > pivot));

//console.log('left ',left);
//console.log("right ",right);

  return [...left,pivot,...right];
}

console.log(quickSort([5, 4, 3, 2, 1, 1, 2])); // [1, 1, 2, 2, 3, 4, 5]

Более элегантным решением было бы удалить стержень из массива перед его фильтрацией. Вместо использования слайса вы можете использовать shift(), чтобы удалить первый элемент из массива. Модифицированное решение становится: 

function quickSort(array) {
  if (array.length <= 1) return array;
  var pivot = array[0];
  // Remove first element
  array.shift()

  var left = quickSort(array.filter(item =>item <= pivot));
  var right = quickSort(array.filter(item =>item > pivot));

  return [...left,pivot,...right];
}

console.log(quickSort([5, 4, 3, 2, 1, 1, 2])); // [1, 1, 2, 2, 3, 4, 5]
...