Implementing Quicksort algorithm in Javascript

by Janeth Kent Date: 16-08-2019 javascript coding functions webdev quicksort

We've been wanting to write an article about sorting algorithms for some time now because sometimes we forget how useful they can be when we want to optimize our code.
So yesterday we played with the quicksort algorithm in Javascript (one of the most efficient when you have to order arrays). In this article we will tell you all the process we have followed.


We hope it will be useful.

Quicksort performance

Worst-case performance: O(n^2)

Best-case performance: O(n log n)

Average performance: O(n log n)

Not bad considering that the bubble sort has an average O(n^2)

How does Quicksort work?

Quicksort works by choosing an element from the array that we'll call a pivot so we can divide the initial array in two:

- the major ones with respect to it

- the minors with respect to it

placing this pivot element in the middle after the separation.

Now for each of these two arrays we will choose a pivot again and repeat the same procedure. There will come a time when the resulting arrays will have either one element or none if there is no longer an element to compare them with. The rest of the elements will have been separated as pivots in some point of the algorithm and they will already be in their correct position.

How do we implement Quicksort?

To implement the quicksort algorithm in javascript we will rely on the pseudocode taken from wikipedia:

algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p - 1)
quicksort(A, p + 1, hi)
algorithm partition(A, lo, hi) is
pivot := A[hi]
i := lo
for j := lo to hi - 1 do
if A[j] < pivot then
swap A[i] with A[j]
i := i + 1
swap A[i] with A[hi]
return i

The first thing we'll do is define the function that executes the algorithm. Since we want to be able to sort all types of arrays (not only numbers, but also objects) we will allow the function to receive by arguments an additional function that specifies the method of sorting objects:

const defaultSortingAlgorithm = (a, b) => {
if (a < b) {
return -1;
}
if (a > b) {
return 1;
}
return 0;
};
const quickSort = (
unsortedArray,
sortingAlgorithm = defaultSortingAlgorithm
) => {
// quicksort implementation
};

If we look at the pseudocode of the wikipedia, we see that as initial pivot is choosing the end of the array (this can cause performance problems increasing it to O(n^2) when the array is already ordered) so not to complicate too much the article we will focus on him. Also, notice that the pseudocode is written in recursive form since we do not know how many partitions we will have to do as we order the array. With all this we come to:

const defaultSortingAlgorithm = (a, b) => {
if (a < b) {
return -1;
}
if (a > b) {
return 1;
}
return 0;
};
const quickSort = (
unsortedArray,
sortingAlgorithm = defaultSortingAlgorithm
) => {
// immutable version
const sortedArray = [...unsortedArray];
const swapArrayElements = (arrayToSwap, i, j) => {
const a = arrayToSwap[i];
arrayToSwap[i] = arrayToSwap[j];
arrayToSwap[j] = a;
};
const partition = (arrayToDivide, start, end) => {
const pivot = arrayToDivide[end];
let splitIndex = start;
for (let j = start; j <= end - 1; j++) {
const sortValue = sortingAlgorithm(arrayToDivide[j], pivot);
if (sortValue === -1) {
swapArrayElements(arrayToDivide, splitIndex, j);
splitIndex++;
}
}
swapArrayElements(arrayToDivide, splitIndex, end);
return splitIndex;
};
// Recursively sort sub-arrays.
const recursiveSort = (arraytoSort, start, end) => {
// stop condition
if (start < end) {
const pivotPosition = partition(arraytoSort, start, end);
recursiveSort(arraytoSort, start, pivotPosition - 1);
recursiveSort(arraytoSort, pivotPosition + 1, end);
}
};
// Sort the entire array.
recursiveSort(sortedArray, 0, unsortedArray.length - 1);
return sortedArray;
};

As you can see, the first thing we do is clone the array so that the function is immutable and we don't modify the input array. From there we define 3 methods:

swapArrayElements: para intercambiar los elementos de un array

partition: que se encarga de elegir el pivote e intercambiar los elementos para que los más grandes estén a su derecha y los más pequeños a su izquierda. Como se puede ver, hacemos la comparación con el método de clasificación que hemos aprobado o con el que hemos establecido por defecto. Este método devuelve la posición en la que se dejó el pivot.

recursiveSort : implementa el algoritmo quicksort definido en wikipedia. Se debe tener en cuenta que es necesario configurar la condición de parada inicio < fin para que de esta forma se interrumpa la recursión si se han alcanzado arrays de 0 ó 1 elementos.

Finally, the quickSort method invokes recursiveSort by passing it the array as well as the initial and final position.
With this we would already have the quicksort algorithm working in javascript:

const testA = [9, -3, 5, 2, 6, 8, -6, 1, 3];
const testASorted = quickSort(testA);
console.log(testASorted);
const testB = [-3, -2, -1, 0, 1, 2, 3];
const testBSorted = quickSort(testB);
console.log(testBSorted);
const testC = [3, 2, 1, 0, -1, -2, -3];
const testCSorted = quickSort(testC);
console.log(testCSorted);
const testD = [
{
id: 9,
name: "Task 9"
},
{
id: -1,
name: "Task -1"
},
{
id: 5,
name: "Task 5"
},
{
id: 3,
name: "Task 3"
},
{
id: -10,
name: "Task -10"
}
];
const testDSorted = quickSort(testD, (a, b) => {
if (a.id < b.id) {
return -1;
}
if (a.id > b.id) {
return 1;
}
return 0;
});
console.log(testDSorted);
 
by Janeth Kent Date: 16-08-2019 javascript coding functions webdev quicksort hits : 6211  
 
Janeth Kent

Janeth Kent

Licenciada en Bellas Artes y programadora por pasión. Cuando tengo un rato retoco fotos, edito vídeos y diseño cosas. El resto del tiempo escribo en MA-NO WEB DESIGN AND DEVELOPMENT.

 
 
 

Related Posts

How to upload files to the server using JavaScript

In this tutorial we are going to see how you can upload files to a server using Node.js using JavaScript, which is very common. For example, you might want to…

How to combine multiple objects in JavaScript

In JavaScript you can merge multiple objects in a variety of ways. The most commonly used methods are the spread operator ... and the Object.assign() function.   How to copy objects with…

The Payment Request API: Revolutionizing Online Payments (Part 2)

In the first part of this series, we explored the fundamentals of the Payment Request API and how it simplifies the payment experience. Now, let's delve deeper into advanced features…

The Payment Request API: Revolutionizing Online Payments (Part 1)

The Payment Request API has emerged as the new standard for online payments, transforming the way transactions are conducted on the internet. In this two-part series, we will delve into…

Let's create a Color Picker from scratch with HTML5 Canvas, Javascript and CSS3

HTML5 Canvas is a technology that allows developers to generate real-time graphics and animations using JavaScript. It provides a blank canvas on which graphical elements, such as lines, shapes, images…

How do you stop JavaScript execution for a while: sleep()

A sleep()function is a function that allows you to stop the execution of code for a certain amount of time. Using a function similar to this can be interesting for…

Mastering array sorting in JavaScript: a guide to the sort() function

In this article, I will explain the usage and potential of the sort() function in JavaScript.   What does the sort() function do?   The sort() function allows you to sort the elements of…

Infinite scrolling with native JavaScript using the Fetch API

I have long wanted to talk about how infinite scroll functionality can be implemented in a list of items that might be on any Web page. Infinite scroll is a technique…

Sorting elements with SortableJS and storing them in localStorage

SortableJS is a JavaScript extension that you will be able to use in your developments to offer your users the possibility to drag and drop elements in order to change…

What is a JWT token and how does it work?

JWT tokens are a standard used to create application access tokens, enabling user authentication in web applications. Specifically, it follows the RFC 7519 standard. What is a JWT token A JWT token…

Template Literals in JavaScript

Template literals, also known as template literals, appeared in JavaScript in its ES6 version, providing a new method of declaring strings using inverted quotes, offering several new and improved possibilities. About…

How to use the endsWith method in JavaScript

In this short tutorial, we are going to see what the endsWith method, introduced in JavaScript ES6, is and how it is used with strings in JavaScript. The endsWith method is…

Clicky