fbpx

Quick sort in JavaScript | Quick and Easy Implementation

Quick sort in JavaScript | Quick and Easy Implementation

Launch the next Yelp in minutes

Download this gorgeous React Native Store Locator app template to create your own store finder app in just a few minutes. By using this fully-coded starter kit written in React Native, you’re saving weeks of design and development and can focus on other important efforts such as customer engagement and marketing.

Check out here

 

Quick sort is one of the most popular and widely-used sort algorithm out there. This algorithm is widely applicable for most of the sort processes. In this tutorial, we are going to implement the algorithm of quick sort in JavaScript.

Well, the sorting mechanism is already implemented in JavaScript as an in-built method sort(). The sort() method in JavaScript uses merge sort algorithm to sort any kind of list or arrays. Indeed, very useful stuff for programmers. It just made sorting so much easier for JavaScript developers. But a programmer must have the knowledge and should be able to implement these algorithms even when the in-build method is not available. Quicksort is comparatively easy to understand and simple to implement.

Thus, this tutorial helps you learn all the nooks and tricks of understanding and implementing the quick sort algorithm in JavaScript.

 

Sorting…

We all know what sorting is. Sorting is the process of arranging the elements any way we want to. In case of programming, we might have come across sorting the arrays or lists in ascending or descending order.

 

What is Quick Sort?

Quicksort is a very efficient algorithm and used widely due to its speed and performance. It has excellent average time complexity of O(N log N) which puts this algorithm over the comparatively less efficient algorithms like bubble sort and insertion sort.

Quicksort uses a divide and conquer algorithm approach.

The idea here is to locate the pivot item in the list by comparing it against all other items in the list. Then, we need to shift items in the lists so that all of the items preceding the pivot item are less than the pivot value and all the items after the pivot item are greater than the pivot value. And then, perform the same operation to the left and right list of items recursively.

Quick Sort Algorithm

  1. First, locate the pivot item in the list or array. This pivot item that we have located is the basis of comparison in this 1st round of operation.
  2. Initialize a left pointer at the first of the list or array.
  3. Initialize a right pointer at the last item of the list or array.
  4. Compare the value of the left pointer in the list/array with the pivot value, if it is less than the pivot value then, move the left pointer to the right and increment by one to the left index position. Continue this operation until the value at the left pointer is greater than or equal to the pivot value.
  5. Compare the value of the right pointer in the list/array with the pivot value, if it is greater than the pivot value then, move the right pointer to the left and decrease by one to the right index position. Continue this operation until the value at the right pointer is less than or equal to the pivot value.
  6. Swap the values at these locations in the list/array, if the left pointer is less than or equal to the right pointer.
  7. Increment the index value of the left pointer to the right by one and the index value of the right pointer to the left by one.
  8. If the left pointer and right pointer do not meet, then repeat the process; else return the index of the left pointer.

 

Implementation of Quick Sort in JavaScript

There are different ways to implement the quick sort in JavaScript. Here, I am going to show you one of the most simple and easy way by creating functions to understand better.

First, we are going to create the swap function which is very simple and easy to understand. The divide function that we are going to implement later depends on the swap function. In swap function, we are just going to follow the sixth step of the algorithm i.e. if the left pointer is less than or equal to the right pointer, we need to swap the values at these locations in the array or list. The code to implement this swap function is provided below in the code snippet:

let swap = (list, leftIndex, rightIndex) => {    

 let temp = list[leftIndex];    

 list[leftIndex] = list[rightIndex];   

 list[rightIndex] = temp;

}

The code above helps to swap the items in the list so that they are in the ascending order.

Second, we are going to create the function to locate the pivot value and divide or partition the list. It is pretty simple and follows the algorithm. The code to implement this function is provided in the code snippet below:

 

let divide = (list, leftPointer, rightPointer)=> {

    let pivotItem   = list[Math.floor((leftPointer  + rightPointer) / 2)],

    while (leftPointer <= rightPointer) {

        while (list[leftPointer] < pivotItem) {
            leftPointer++;
        }

        while (list[rightPointer] > pivotItem) {
            rightPointer--;
        }

        if (leftPointer <= rightPointer) {
            swap(list, leftPointer, rightPointer);
            leftPointer++;
            rightPointer --;
        }

    }
    return leftPointer;

}

The function above partitions the list into left and right and returns the value of the left pointer. The value of the left pointer is returned because its value is used to locate the partitioning position in the next round.

Now, let us round this all up and create a quick sort function that performs all the action at once. With all the partitioning and swapping being performed in the above functions, it makes the basic function for quicksort simple and easy to implement. The code for implementing quick sort function is given in the code snippet below:

let quicksort = (list, leftIndex, rightIndex) => {     

  let indexItem;    

  if (list.length > 1) {        

    indexItem = divide(list, leftIndex, rightIndex);         

    if (leftIndex < indexItem - 1) {            

      quickSort(list, leftIndex, indexItem - 1);       

    }         

    if (indexItem < rightIndex) {            

      quickSort(list, indexItem, rightIndex);        

    }    

  }     

  return list;

} 

let result = quickSort(list, 0, list.length - 1);  

list = [2,5,10,12,6,3,7] 

Output  : [2,3,5,6,7,10,12]

 

The quicksort function takes three arguments i.e. list, left index for left pointer and right index for right pointer and then performs all the operations as per the algorithm. It performs the partition and recursive calls itself until the list of item is sorted out completely.

 

This completes our implementation of the quick sort in JavaScript.

Krissnawat Kaewsanmuang

Fullstack Javascript developer from beautiful Chiangmai, love Americano and travel so much

Leave a Reply

Your email address will not be published. Required fields are marked *