QuickSort Algorithm Simplified
Tags: javascript, algorithms, quicksort
Published: 2022-02-09 16:34:06

QuickSort is a sorting algorithm that uses a divide and conquer strategy to sort out elements in an array. This strategy uses the following steps:

1. Selects a pivot element from the array, which can be picked in various ways.
    - Pivot set from the first element.
    - Pivot set from the last element.
    - Set a random element as a pivot.
    - Use median as the pivot.
2. Uses the pivot to divide the array into subarrays. This process is called partitioning. The pivots partitions elements less than itself to the left side, and elements that are greater are to the right of the pivot.
3. Recursively splits the left and right subarrays using the 1st and the 2nd step until each subarray has one element left.
4. Once the process is complete, the element already gets sorted. Finally, combines the sorted elements back to an array.

## QuickSort Partitioning Algorithm with Javascript

Here is an example of a quicksort function in javascript with a breakdown process of each statement.

```jsx
const nums = [6,5,2,9,1,3,11,4];
function qSort(arr){
  
    if(arr.length <= 1){
        return arr
    } 
    let pivot = arr.pop(), left = [], right = [], newArray =[],  length = arr.length
     for(let index = 0; index < length; index++){
     if(arr[index] <= pivot){
         left.push(arr[index])
          }
          else{
            right.push(arr[index])
          }
        }
   return newArray.concat(qSort(left), pivot, qSort(right))
}
```

1. First, an array of unsorted elements are created.

    ```jsx
    //nums is the given array
    const nums = [6,5,2,9,1,3,11,4];
    ```

2. Then the function `qSort`, to perform the quicksort algorithm. With the `arr` parameter to receive the array.
    
    ```jsx
    //QuickSort Function
    function qSort(arr){
    
    }
    ```
    
3. A condition is then set to make sure the array (`arr`) provided is not empty and does not contain only one element. *If* the array has less than one element, it will *return* that array but proceeds to the next step if it includes more than one element.
    
    ```jsx
    function qSort(arr){
    	  // if array contains less than one element, return the array
        if(arr.length <= 1){
            return arr
        } 
    		// if array contains more than one element, proceed to next statement
    ```
    

4. The next step is to choose a pivot. In this case, the pivot is set to pick only the last element in the array with the `left` and `right` array for partitioning. `newArray` will append all elements to a new sorted array.
    
    ```jsx
    let pivot = arr.pop(), left = [], right = [], newArray =[], length = arr.length
    ```
    
    ![Selecting last element as pivot](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/z6el31b0hnia6pbat94p.png)

    
    A `left` and `right` array are created to partition the elements for the pivot. The pivot position lesser elements to the left and greater elements to the right.
    
    
    
    ![Pivot positioning](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zhxd3fbut1ow0i6dcyjx.png)
    
    ```jsx
    let pivot = arr.pop(), left = [], right = [], newArray =[], length = arr.length
    	for(let index = 0; index < length; index++){
    		// push elements less than pivot to the left
      if(arr[index] <= pivot){
    	  left.push(arr[index])
       }
    		// push elements higher than pivot to the right
       else{
         right.push(arr[index])
       }
    ```
    
    This process continuous and breaks into partitions until one element is left.
    
    
    ![Partition breakdown](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gp2vgm83dpjtxbnu7d5l.png)
    
4. At this point, all elements in the array are finally sorted. The last step returns all sorted elements to the `newArray` by concatenating the `left`, the `pivot`, and the `right` array.

    ```jsx
    let pivot = arr.pop(), left = [], right = [], newArray =[], length = arr.length
     for(let index = 0; index < length; index++){
		// push elements less than pivot to the left
      if(arr[index] <= pivot){
	  left.push(arr[index])
      }
		// push elements higher than pivot to the right
       else{
         right.push(arr[index])
       }
    return newArray.concat(qSort(left), pivot, qSort(right))
    ```

You can test the code using this link - [Run quicksort  with javascript](https://jsfiddle.net/wonexo/dk2qynts/4/).

## How long it takes to run QuickSort Algorithm

There are three different time cases it will take the algorithm to run. The best case, worst case and average case.

1. **Best Case** *[O(nlog n)]*: The algorithm runs faster than other cases when the pivot is always selected at the middle element.  
    
    ![Best case](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bxv5po6xkai33qvq886v.png)
    
2. **Worst Case** *[O(n2)]*: This happens when the pivot selected is the largest or smallest element leaving one of the sub-arrays always empty.
    
    
    ![Worst Case](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kathyjfl17a7py1b3fhd.png)
    
3. **Average Case** *[O(n*log n)]*: This case happens when none of the above occur.

To get more information about quicksort algorithm you can check the following links below:

- [Quicksort algorithm by programiz](https://www.programiz.com/dsa/quick-sort)
- [Quicksort algorithm by geeksforgeeks](https://www.geeksforgeeks.org/quick-sort/)
- [Quicksort from wikipedia](https://www.geeksforgeeks.org/quick-sort/)