Published
Edited
Oct 5, 2022
1 star
Quicksort
The quicksort picks a value, then moves all elements smaller to the left and larger to the right.
Then this is repeated for the left and right parts until all elements are internally sorted.
function partition(arr, start, end) {
// pick a pivot point
let pivotValue = arr[end - 1]
// keep track of where the pivot will end up, this will move as we identify its position in the array
// we begin by assuming it will be the first element
let pivotIndex = start
for (let i = start; i < end - 1; ++i) {
let elementValue = arr[i]
if (elementValue < pivotValue) {
// it should be left of the pivot meaning
// replace the current pivot position with this
arr[i] = arr[pivotIndex]
arr[pivotIndex] = elementValue
// and set the new pivot position to the element right of this
pivotIndex++
}
}
// Finally, place the pivot value where it should be
arr[end - 1] = arr[pivotIndex]
arr[pivotIndex] = pivotValue
return pivotIndex
}
function examplePartition(arr, start, end) {
const index = partition(arr, start, end)
return `Partition around arr[${index}] = ${arr[index]}, result ${arr}`
}
examplePartition([1, 7, 2, 3, 5], 0, 5)
examplePartition([9,8,6,6,5,3,2], 0, 7)
examplePartition([1, 2, 3], 0, 3)
examplePartition([3,1,2], 0, 3)
// 1 2 3
function _quicksort(arr, start, end) {
if (start < end) {
const partitionIndex = partition(arr, start, end)
// sort up until the partition point and right of it
_quicksort(arr, start, partitionIndex)
_quicksort(arr, partitionIndex + 1, end)
}
return arr
}
function quicksort(arr) {
return _quicksort(arr, 0, arr.length)
}
quicksort([2,2,1,5,7,8,9,123,2,1,25,623])
quicksort([34,921,122121,212,2,4,5,9,2,1,2,40,-212,21,-42342,932])
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
