quick-sort.ts
function quicksort(array: number[], left: number, right: number) {
if (left >= right) {
return
}
const pivot = array[Math.floor((left + right) / 2)]
const index = partition(array, left, right, pivot)
quicksort(array, left, index - 1)
quicksort(array, index, right)
}
function swap(array: number[], left: number, right: number) {
const t = array[right]
array[right] = array[left]
array[left] = t
}
function partition(
array: number[],
left: number,
right: number,
pivot: number
) {
while (left <= right) {
while (array[left] < pivot) {
left++
}
while (array[right] > pivot) {
right--
}
if (left <= right) {
swap(array, left, right)
left++
right--
}
}
return left
}
const array = [2, 5, 7, 8, 9, 5, 9, 20, 11, 43, 80]
quicksort(array, 0, array.length - 1)
console.log(array)