Update: further succinct versions below (inspired by Haskell)
Quick sort in JS assuming an immutable array:
const reorder = (arr, pivot) => {
let larger = []
let smaller = []
let equals = []
for (let i = 0; i < arr.length; i++) {
if (arr[i] < arr[pivot]) {
smaller.push(arr[i])
} else if (arr[i] > arr[pivot]) {
larger.push(arr[i])
} else {
equals.push(arr[i])
}
}
return {
smaller: smaller,
equals: equals,
larger: larger
}
}
const sort = (arr) => {
if (arr.length <= 1) {
return arr
}
const pivot = Math.floor(arr.length / 2)
const result = reorder(arr, pivot)
return [...sort(result.smaller), ...result.equals, ...sort(result.larger)]
}
console.log(sort([3, 1, 1, 1, 2]))
PS: I deleted the question posted earlier, thinking the algo was wrong, but then I realized a small tweak corrected it. The present code is based on comments received on earlier question.
Update: Inspired by Haskell, here is a more succinct version using ES6:
const qsort = (arr) => {
if(arr.length == 0) {
return []
}
let [x,...xs] = arr
let smaller = xs.filter(v => v <=x)
let larger = xs.filter(v => v > x)
return [...qsort(smaller),x,...qsort(larger)]
}
OR simplified further:
const qsort = ([x,...xs]) => {
return x == undefined ? [] :
[...qsort(xs.filter(v => v <=x)),x,...qsort(xs.filter(v => v > x))]
}
qsort([3,3,8,1,23,4,5,6,9,9,1,0,45,5,10])
return !x ? [] :
this will return an empty array when the first element is 0. \$\endgroup\$ – Kruga Jul 18 at 9:35