Quicksort is a sorting algorithm. It's a divide-and-conquer algorithm that sorts a sequence by recursively dividing it into smaller subsequences. Let's see our function:
function quick_sort(array) {
if(array.length < 2) return array;
const pivot = array[0];
let lower = array.filter(e => e < pivot),
greater = array.filter(e => e > pivot);
return [...quick_sort(lower), pivot, ...quick_sort(greather)];
}
quick_sort([7,5,9,4,8,2])
Empty arrays and arrays with just one element are the base case. Nothing to sort here, and we can just return those arrays as is.
Quicksort algorithm starts with picking a pivot. There are many ways to choose a pivot:
• 1st element (as we do)
• last element
• median of the array as a pivot
• a random element as the pivot
const pivot = array[0];
After filtering collection (array) we have:
• A sub-array of all the numbers lower than the pivot
• The pivot
• A sub-array of all the numbers greater than the pivot
return [...quick_sort(lower), pivot, ...quick_sort(greater)];
Call quicksort recursively on the two sub-arrays (lower and greater) to break down the collection into single-element lists (hitting the base case), before combing them into one sorted list.
Top comments (0)