DEV Community

Duncan McArdle
Duncan McArdle

Posted on

1

Quick Sort (JavaScript)

Quick sorting is a sorting algorithm that focuses on placing a single value of an array in its correct position for each iteration. It does this by splitting the array at a pivotal point (called the pivot), and then moving all numbers greater than that pivot to be after it, and all numbers less than the pivot to be before it.

For example, given the array [3, 7, 4, 5, 9], you might select a pivot point of index 3 (which has a value of 4 in the above array). You would then go through each number and ask “Is it greater than or less than the pivot?”. In the above example, 3 would be less and so remain as-is. 7 would be greater and so be pushed beyond the pivot. 5 and 9 are then both greater and so remain where they are. So what we’re left with is an array of [3, 4, 7, 5, 9], where the pivot number (4) is now in the correct place in the array.

From there, we can then repeat the process on the values either side of the array recursively, until every value in the array is correctly placed.

In my opinion, quick sort isn’t a great method of sorting. There are far too many arbitrary aspects for how your code can work that make it less of an algorithm and more of an idea, and that makes implementation difficult to understand, as everyone has a slightly different method. In addition, it doesn’t resemble any real-life method of sorting, so I find it a little less intuitive than most. That said, most implementations do share key concepts, so if you can learn those, it makes everything a little bit easier.

In addition, although not my favourite in terms of how it works, what I do like is that it performs the sorting operation in-memory, something you may sometimes be asked to do specifically.

Below are two similar but different methods of implementing quick sort in JavaScript. Both follow the same pattern; we choose a pivot, split the array in 2 (one side with values less than the pivot, the other side with values greater than it), and then repeat the process for each part, until we eventually have a sorted array. Both also have the same final step; after sorting the non-pivot contents of the array, we then place the pivot in between both sides, so as to “correctly” place it.

Method #1: For loop

In this method, we make our pivot our right-most element (so as to make the for loop more readable, as it can still go left-to-right). Then we loop through all of the elements in the array, and move those lower than the pivot to the left hand side, and those greater than it to the right hand side. Finally, we place the pivot in the middle of all these numbers (technically, we swap it for the lowest number that is greater than the pivot), and we have then found the correct placement for the pivot.

function quickSort(nums) {
function recursiveQuickSort(nums, leftIndex, rightIndex) {
// Run until we have less than 2 elements to sort
if (leftIndex >= rightIndex) {
return;
}
// Correctly place a number within the current range
const partitionIndex = partititon(nums, leftIndex, rightIndex);
// Call the function again on either side of the correctly sorted number
recursiveQuickSort(nums, leftIndex, partitionIndex - 1);
recursiveQuickSort(nums, partitionIndex + 1, rightIndex);
}
function partititon(nums, leftIndex, rightIndex) {
// Choose a pivot point (right-most value)
const pivotIndex = rightIndex;
// Create a marker to show where the first greater-than-pivot number is stored
let firstGreaterThanPivotIndex = leftIndex;
for (let i = leftIndex; i < rightIndex; i++) {
// If the current number is less than the pivot
if (nums[i] <= nums[pivotIndex]) {
// Swap the current number with the first greater than pivot number
[nums[i], nums[firstGreaterThanPivotIndex]] = [
nums[firstGreaterThanPivotIndex],
nums[i],
];
// Increment the first greater than pivot counter, as the number in that position is now lower than the pivot
firstGreaterThanPivotIndex++;
}
}
// Place the pivot in the middle of the sorted values, swapping it for the first higher-than-pivot value
[nums[firstGreaterThanPivotIndex], nums[pivotIndex]] = [
nums[pivotIndex],
nums[firstGreaterThanPivotIndex],
];
return firstGreaterThanPivotIndex;
}
recursiveQuickSort(nums, 0, nums.length - 1);
}

This method was inspired by this great video from mycodeschool, which I recommend you check out once you grasp the above.

Method #2: While

In this method, we make our pivot the left-most element. Next we place markers at the next element in the array, and the final element of the array. Now, we move the left-marker right until we find a value that is greater than the pivot, and we move the right-marker left until we find a value that is lower than the pivot. In other words, we constrict the window of observation until we find numbers that belong on the opposite sides. Then we swap these values, so that they are now on the correct sides, and then continue until our markers meet. Finally, we place the pivot in the middle of all these numbers, and we have then found the correct placement for the pivot.

function quickSort(arr) {
function recursiveQuickSort(leftIndex, rightIndex) {
// Run until we have less than 2 elements to sort
if (leftIndex >= rightIndex) return;
// Correctly place a single value and obtain its index
const sortedPoint = sortAndReturnSortedIndex(leftIndex, rightIndex);
// Sort each side of the correctly sorted index
recursiveQuickSort(leftIndex, sortedPoint - 1);
recursiveQuickSort(sortedPoint + 1, rightIndex);
}
function sortAndReturnSortedIndex(leftIndex, rightIndex) {
// Use the right-most value as the pivot
const pivotIndex = rightIndex;
// Decreate the right-index so as to skip the pivot
rightIndex--;
// Run until the contracted window has fully contracted
while (leftIndex < rightIndex) {
// Move the left-index right until it finds a value higher than the pivot
while (arr[leftIndex] < arr[pivotIndex]) leftIndex++;
// Move the right-index left until it finds a value lower than the pivot
while (arr[rightIndex] > arr[pivotIndex]) rightIndex--;
// Swap the left and right values, so long as the window hasn't fully contracted
if (leftIndex < rightIndex) {
[arr[leftIndex], arr[rightIndex]] = [arr[rightIndex], arr[leftIndex]];
}
}
// The left-index stopped when it reached the first value greater than the pivot
// So swap the pivot for the left-index, and the pivot is now correctly placed
[arr[leftIndex], arr[pivotIndex]] = [arr[pivotIndex], arr[leftIndex]];
return leftIndex;
}
// Start the sorting process
recursiveQuickSort(0, arr.length - 1);
}

This method was inspired by this great video from Abdul Bari, which I recommend you check out once you grasp the above.

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

The Most Contextual AI Development Assistant

Pieces.app image

Our centralized storage agent works on-device, unifying various developer tools to proactively capture and enrich useful materials, streamline collaboration, and solve complex problems through a contextual understanding of your unique workflow.

👥 Ideal for solo developers, teams, and cross-company projects

Learn more

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay