# Quick Sort Algorithm Using JavaScript

### Introduction

Quicksort is a popular sorting algorithm that follows the `divide-and-conquer algorithm`. The `divide-and-conquer algorithm` is an approach to solving a large problem by breaking it down into smaller sub-problems recursively. If the sub-problems are small enough, they can now be combined to get the desired output.

### How does Quicksort Algorithm work?

Quicksort algorithm works by selecting a `pivot` which could be any number from an array and then partitioning the array into two sub-arrays where the elements with lesser values come before the `pivot` and elements with greater values come after the `pivot`. Then the process is carried out recursively on the sub-arrays of elements with lesser values and separately on sub-arrays of elements with greater values until each sub-arrays contains a single element and the elements can now be combined to form a sorted array.

Pivot selection is an important part of the Quicksort algorithm and there are many techniques that can be used. You can select :

- the first element as the pivot

- the last element as the pivot

- the median number as the pivot

- a random number as the pivot

### Visual representation of the Quick Sort Algorithm 


![A5 - 1.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1642186433055/6hWlajbUG.png)

### Implementing Quicksort Algorithm in JavaScript

```
function Quicksort(array){
    if(array.length <= 1){
        return array;
    }
    const pivot = array[array.length - 1 ]
    const leftArray = []
    const rightArray = []
    for(let i = 0; i < array.length - 1; i++){
        array[i] < pivot ? leftArray.push(array[i]) : rightArray.push(array[i])
    }
    return[...Quicksort(leftArray), pivot, ...Quicksort(rightArray)]
}
const Arr =[1, 4, 9, 8, 245, 123, 43, 62, 3978, 27, 123, 43, 2, 58, 1, 76, 82]
console.log(Quicksort(Arr))
```
**output:**

```
[ 1,  1,  2,   4,   8, 9,   27, 43,  43,  58, 62, 76, 82, 123, 123, 245, 3978 ]
```

![Copy of Copy of hooks (2).png](https://cdn.hashnode.com/res/hashnode/image/upload/v1642327945649/6MLY8RmmL.png)
Let's take a look at how the example is implemented ⬇️ 

- Declare a function that holds a parameter called `array`.

- Now you'll declare an `If statement` to check the length of the array. If the length is less than or equal to one, you'll return the array unaltered.

```
 if(array.length <= 1){
        return array;
    }
```

- Next, you'll select a pivot element which is the last element in the array in this case.

```
const pivot = array[array.length - 1 ]
```


- Then you will create two empty arrays which are the `leftArray` and `rightArray` to compare elements with pivot and place the element accordingly.

```
const leftArray = []
const rightArray = []
```

- You will iterate through the array by using a for loop and inside this loop, you will want to check if the element is lesser or greater than the pivot. If the element is lesser than the pivot, you'll push it into the `leftArray` and if the element is greater than the pivot, you'll push it into the `rightArray`.

```
 for(let i = 0; i < array.length - 1; i++){
        array[i] < pivot ? leftArray.push(array[i]) : rightArray.push(array[i])
    }
```

- Lastly, you will call the Quicksort function recursively on the left and right array to partition the arrays until they get sorted completely.

```
 return[...Quicksort(leftArray), pivot, ...Quicksort(rightArray)]
```
### References

- [Youtube](https://www.youtube.com/watch?v=XE4VP_8Y0BU) 
- [Github](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/quick-sort) 
-  [Khanacademy](https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/overview-of-quicksort)