Skip to content

Instantly share code, notes, and snippets.

@kangax

kangax/quicksort.hs

Last active September 5, 2021 19:44
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save kangax/6c4407941d976fe00948 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save kangax/6c4407941d976fe00948 to your computer and use it in GitHub Desktop.
Download ZIP
Haskell-inspired quick sort in ES6
Raw
quicksort.hs
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
let smallerSorted = quicksort (filter (<=x) xs)
biggerSorted = quicksort (filter (>x) xs)
in smallerSorted ++ [x] ++ biggerSorted
Raw
quicksort.js
/*
1) passing array
> quicksort([4,3,2,1]); // => [1,2,3,4]
*/
function quicksort(tail) {
if (tail.length === 0) return [];
let head = tail.splice(0, 1)[0];
return quicksort(tail.filter( _ => _ <= head))
.concat([head])
.concat(quicksort(tail.filter( _ => _ > head )))
}
/*
2) via arguments
> quicksort(4,3,2,1); // => [1,2,3,4]
or:
> quicksort(...[4,3,2,1]); // => [1,2,3,4]
*/
function quicksort(x, ...xs) {
if (arguments.length === 0) return [];
return quicksort(...xs.filter( _ => _ <= x))
.concat([x])
.concat(quicksort(...xs.filter( _ => _ > x )))
}
@wjramos
Copy link

wjramos commented Apr 21, 2021 •
edited
Loading 

function quickSort(values = []) {
  const [pivot, ...restValues] = values;
  
  if (!pivot) return [];
  if (!restValues.length) return [pivot];
  
  const [lesser, greater] = restValues.reduce((partitions, val) => {    
    partitions[+(val > pivot)].push(val);

    return partitions;
  }, [[], []]);
  
  return [
    ...quickSort(lesser),
    pivot,
    ...quickSort(greater),
  ];
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment