D
D
depstor2020-05-02 00:25:28
JavaScript
depstor, 2020-05-02 00:25:28

How can I set the sort order (ascending or descending) in the Quicksort function?

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

I wrote the quickSort function, now I want to pass it 2 parameters, the array itself and the sorting method (from a smaller number to a larger one, or vice versa), but I can’t break the function, can someone help?

What would be: function quickSort(arr, a или b)where "a" sorts the array as [1, 2, 3]and "b" sorts the array as [3, 2, 1].

Answer the question

In order to leave comments, you need to log in

2 answer(s)
R
Rsa97, 2020-05-02
@Rsa97

You have an error. If there are several values ​​in the array equal to pivot, then only one will remain, the rest will be lost.
Optimally, changing the sort direction is done by passing a callback function that defines the relationship between two elements. Then you can sort not only numbers, but also any elements for which an order is defined.

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

I
Ivan Klimenko, 2020-05-02
@yeswell

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

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question