Как задать порядок сортировки (по возрастанию или по убыванию) в функции Quicksort?

Question

[depstor]

const arr = [1, 200, 49, 32, 78, 100];
const a = value => value < pivot;

const quickSort = (arr) => {
    if (arr.length < 2) {
        return arr;
    } else {
        const pivot = arr[Math.floor(Math.random() * arr.length)];
        const less = arr.filter(value => value < pivot);
        const greater = arr.filter(value => value > pivot);
        return [...quickSort(less), pivot, ...quickSort(greater)];
    }
}

Написал функцию quickSort, теперь хочу передавать ей 2 параметра, сам массив и способ сортировки (от меньшего числа к большему, либо наоборот), но не могу разбить функцию, кто-то может помочь?

Что бы было так: function quickSort(arr, a или b), где "а" сортирует массив как [1, 2, 3], а "b" сортирует массив как [3, 2, 1].

Answer 1

[Rsa97]

У вас ошибка. Если в массиве будут несколько значений, равные pivot, то останется только одно, остальные пропадут.
Оптимально смена направления сортировки делается через передачу callback-функции, определяющей отношение между двумя элементами. Тогда можно сортировать не только числа, но и любые элементы, для которых определён порядок.

const defaultOrder = (a, b) => a < b ? -1 : a > b ? 1 : 0
const qSort = (arr, order = defaultOrder) => {
  if (arr.length < 2) {
    return arr;
  }
  const pivot = arr[Math.floor(arr.length * Math.random())]
  const less = arr.filter(a => order(a, pivot) < 0)
  const equal = arr.filter(a => order(a, pivot) === 0)
  const greater = arr.filter(a => order(a, pivot) > 0)
  return qSort(less, order).concat(equal).concat(qSort(greater, order))
}

Comments

[depstor]

у меня ошибки идут
и где тут аргументы на разную сортировку ?

[Иван Клименко]

Вы, конечно, сделали некоторое количество ошибок

[Rsa97]

Иван Клименко, Да, написал с ходу без проверки. Поправил.

[Rsa97]

depstor, Аргументом определяющим сортировку является callback-функция order. Она должна для пары элементов массива возвращать значение меньшее нуля, если первый элемент должен идти перед вторым, ноль если порядок элементов одинаковый, больше нуля если первый элемент должен идти после второго.
Аналогичную функцию использует стандартный метод Array.sort()

[Иван Клименко]

Rsa97, а вы всё равно при рекурсивном вызове не передаёте функцию сравнения =)

[depstor]

Rsa97, Не то что я хотел

Answer 2

[Иван Клименко]

function qSort(array, comparator, divider) {
    if (array.length < 2) {
        return array;
    }
    const defaultComparator = (a, b) => ((a < b) ? -1 : ((a > b) ? 1 : 0));
    const defaultDivider = array => array[Math.floor(array.length * Math.random())];
    const getOrder = comparator || defaultComparator;
    const getPivot = divider || defaultDivider;
    const pivot = getPivot(array);
    const less = [], equal = [], greater = [];
    for (const item of array) {
        const order = getOrder(item, pivot);
        const subArray = ((order < 0) ? less : ((order > 0) ? greater : equal));
        subArray.push(item);
    }
    return [...qSort(less, getOrder, getPivot), ...equal, ...qSort(greater, getOrder, getPivot)];
}

Comments

[depstor]

выводит так [ 1, 32, 49, 78, 100, 200 ], а аргумент что бы выводить в обратную сторону , но именно передавая аргумент ?