quicksort

quicksort.ts

const arr = [ 100, 1,3,4,6,0,8,11, 2,30,5];

function sort<T>(items: T[]) {
  const copy = [...items];
  quickSort(copy);
  return copy;
}

function quickSort<T>(items: T[], start: number = 0, end:number = items.length) {
  const length = end - start;
  if(length <= 1) {
    return;
  }
  const selectedPivotIndex = start + Math.floor(Math.random() * length);
  swap(items, start, selectedPivotIndex);

  const selectedPivotValue = items[start];
  let partitionIndex = start;

  for(let i = start + 1; i < end; i++) {
    if(items[i] < selectedPivotValue) {
      partitionIndex++;
      swap(items, i, partitionIndex);
    }
  }

  if(partitionIndex !== start) {
    swap(items, start, partitionIndex);
  }

  quickSort(items, start, partitionIndex);
  quickSort(items, partitionIndex + 1, end);
}

function filteredQuicksort<T>(items: T[]) {
  if(items.length <= 1) {
    return items;
  }

  const pivot = items[items.length - 1];

  return [
    ...filteredQuicksort(items.filter(lessThan(item => item < pivot))),
    pivot,
    ...filteredQuicksort(items.filter(greaterThan(item => item > pivot)))
  ]
}

function lessThan<T>(filterFn: (item: T) => boolean) {
  return (item: T, idx: number, items: T[]) => filterFn(item) && idx < items.length - 1;
} 
function greaterThan<T>(filterFn: (item: T)=> boolean) {
  return (item: T, idx: number, items: T[]) => filterFn(item) && idx < items.length - 1;
} 

function swap<T>(items: T[], a: number, b: number) {
  [items[a], items[b]] = [items[b], items[a]];
}

console.log(sort(arr));
console.log(filteredQuicksort(arr));