JavaScript ECMAScript 6 Quick Sort Algorithm Tutorial

There are tons of Algorithms that programmers solve through various approaches.

Algorithms are often asked in programming interviews to ascertain the candidates’ caliber in solving a programming problem.

In this tutorial, you will learn how to sort the random numbers array using the QuickSort linear search algorithm in JavaScript.

We will use the recursive function approach to write the quick sort algorithm program and show you how to write the quick sort algorithm using EcmaScript 6 syntaxes.

Also, show you how to write the quick sort algorithm using EcmaScript syntaxes and, yes, the recursive function approach too.

Sort Array of Numbers with QuickSort Algorithm in JavaScript / EcmaScript 6

• Step 1: What is Algorithm?
• Step 2: Introduction to Quick Sort
• Step 3: Pivot in Divide & Conquer
• Step 4: Recursive Function
• Step 5: Break Down Quick Sort Algorithm Logic
• Step 6: Quick Sort Code Example
• Step 7: Quick Sort Time Complexity
• Step 8: Test Algorithm

What is Algorithm?

The word algorithm is not just limited to programming. It is a set of instructions followed to solve a problem in conjunction with completing a particular task.

The simplest example of an algorithm could be taken from your daily life. Often you go to the office from home.

If you carefully see the whole process, you will notice a chain of tasks that you have to complete respectively to accomplish the task. Such as:

• Step 1: Wake up in the morning.
• Step 2: Get fresh and dressed well.
• Step 3: Have breakfast.
• Step 4: Leave home at a particular time.
• Step 5: Use car or bus or public transport to commute.
• Step 6: Reach to office location.
• Step 7: Enter the office building
• Step 8: Sit at your place in the office and start working.

As you can see, these are the smaller tasks that you have to complete to reach to the office from home.

On the same pattern, in computer programming algorithms are written to write a better programme that solves a bigger problem step by step.

As a programmer, you have to visualize those tasks in mind, note down on paper. Align, smaller tasks step-by-step in coding and solve the programming problem.

Introduction to Quick Sort

QuickSort algorithm works on the divide and conquer principle. In the divide and conquer approach, array elements are arranged based on partitioning.

Partitioning or smaller groups of the array are used to bring the data in sorted form with the help of the pivot element.

Pivot in Divide & Conquer

The pivot is the most important element in Quick Sort algorithm. The pivot value is taken from the array. The pivot is used to compare array values with each other.

By comparing pivot with different values, you can easily determine whether the current value is greater or smaller in size and in which partition it should be kept. You can set pivot point left most, right most or middle element from the array.

After categorizing the array values using pivot point, time comes to print the sorted array using the recursive function.

Recursive Function

A recursive function is a function that invokes itself as long as the given condition is true. Recursive functions are best used with quick-sort and linear and binary search. Undoubtedly, it helps break down the multiple tasks into smaller ones.

Break Down Quick Sort Algorithm Logic

Here are the steps that we used to write a quick sort algorithm programme in JavaScript:

• Create the number array.
• Use const to create a quickSort(array) function that takes an array as an argument.
• Check if the array has only one element print the array.
• Set rightmost element as pivot.
• Set two empty arrays, smaller numbers than pivot value go into a left array; similarly, a bigger number than pivot goes into the right array.
• Iterate over the array; make sure to skip the last element of the array because we made it a pivot point.
• Set the if condition and check if the current array item is less than the pivot. If yes, push it into the leftArray. If the current array element is greater, then pivot then put it into the rightArray.
• Now, the two subgroups are made in which we added the elements. Next, we will use the recursive functions with spread operators to solve the quick sort algorithm.
• We have possibilities both left, and right array may have the number values. Only the left array has the numerical values, or perhaps only the right array has the values. Consequently, to handle such a scenario, use the recursive function with a spread operator to sort the array.

EcmaScript Quick Sort Algorithm Full Code Example

To sort the number values in the array, you must add the given code in your code file. In the subsequent step, we will enumerate how the quick sort is created and working.

let myArr = [22, 19, 22, 10, 5, 55, 33, 10, 8, 45, 55, 99, 17]
const quickSort = (arr) => {    
    // If array lenght is limited to 1
    if(arr.length === 1) {
        return arr;
    }
    
    // Make right most element of the arrey the pivot point.
    let pivot = arr[arr.length - 1];
    
    /* Set two empty arrays, smaller element than pivot point goes into left array, 
       likewise, bigger elements than pivot element goes into right array.
    */
    let leftArray = [];
    let rightArray = [];
    // Iterate over the array, skip last pivot element.
    for(let i = 0; i < arr.length - 1; i++) {
       // Check if the current item is smaller than pivot, put it in left array otherwise keep in right array.
       if(arr[i] < pivot) {
           leftArray.push(arr[i]);
       } else {
           rightArray.push(arr[i]);
       }
    }
    if(leftArray.length > 0 && rightArray.length > 0) {
        return [...quickSort(leftArray), pivot, ...quickSort(rightArray)]
    } else if (leftArray.length > 0) {
        return [...quickSort(leftArray), pivot]
    } else {
        return [pivot, ...quickSort(rightArray)]
    }
}
console.log(quickSort(myArr))

Quick Sort Time Complexity

We have sorted the array using the quick sort approach; the method we used in the above code example is Partitioning.

Further, we will let you know about the quick-sort time complexities for best, worst and average case scenarios.

Best time complexity: n*log(n)

Worst-case complexity: n^2

Average time complexity: n*log(n)

Test Algorithm

Now, you can test the code of the algorithm, after the algoritm invokes you will have the sorted arrays as follows:

[5,  8, 10, 10, 17, 19, 22, 22, 33, 45, 55, 55, 99]

Conclusion

The path to becoming a great JavaScript developer is not so facile; you have to learn tons of things. The quicksort algorithm simply sorts the number arrays; we went through many concepts to solve the array in this tutorial.

However, JavaScript offers a sort() method that can solve your purpose without putting so much effort. But, working on an algorithm develops your skills and makes you familiar with the knitty gritty of programming.

I hope this guide will help you get closer to be a sublime developer.