Quicksort

Hey Devs,

Imagine attending an interview, and the interviewer asks you to sort an array without using built-in methods. It is a common interview question for beginners to test their understanding of a particular programming language. What would you do?

Don't worry. The quicksort algorithm has got you covered.

What is Quick Sort?

Quicksort is a divide-and-conquer algorithm that breaks down a problem into smaller sub-problems, solves the subproblems recursively, and then combines the solutions to the subproblems to solve the original problem.

In this we are going to use javascript.

We need to write a function that accepts an array as a parameter to implement quick sort.
```
 const quickSort = (arr) => {
     //...
     //...
 }
```

Since this is a recursive solution, we need an escape case.

 const quickSort = (arr) => {
     if (arr.length <= 1) {
         return array
     }
 }

Divide and Conquer algorithm will divide the problem. We are using recursion for DAC. The base case is used to escape from the recursion . If an array has only one element, then it's already sorted. We use this rule to divide the array into smaller arrays until it becomes an array with only one element using recursion.
In the base case, If an array's length is less than or equal to one, it will return the array. The recursion will escape out of the loop.

Time to divide and conquer. The quick sort needs a pivot element. So, what is a pivot element? A pivot element is used for dividing an array into smaller sub-arrays. The pivot element can be the first, last or middle element in an array. In this example, we are going to take the first element as pivot.
```
  const pivot = arr[0];
```
We are going to divide the array into two subarrays. For that, let's create two subarrays.
```
  const lessThan = [];
  const greaterThan = [];
```
- The lessThan array stores the values less than the pivot. The greaterThan array stores the values higher than the pivot. With the help of a for loop, we divide the array into smaller sub-arrays.

     for (let i = 1; i < len; i++) {
          if (arr[i] < pivot) {
            lessThan.push(arr[i]);
          } else {
            greaterThan.push(arr[i]);
          }
        }

The array is divided into two sub-arrays. The array remains unsorted need to worry. With the help of recursion, We apply the quicksort to the lessThan and greaterThan array until it becomes a single array and escapes the loop.
- Recursion - Think of a recursion as a box inside a box that is within a box. The gift we want is in the innermost box. To get our gift, First, we need to unwrap the outer box and go on until we reach the final box. Now we can get our gift. This flow represents how a recursion works. A function calls itself again and again until a condition is satisfied. If we forget to mention the condition, it'll run indefinitely.

The Image is a simple representation of how the quick sort algorithm works. First, we select a pivot element. Based on the pivot, We divide the arrays and repeat until every array has exactly one element.

Time to return the result!

  return [...quickSort(leftArr), pivot, ...quickSort(rightArr)];

... This is a spread operator in javascript which is used to copy the values from an array. Hooray we did it.

The Solution - Quick Sort Algoirthm

const quickSort = (arr) => {
    const len =arr.length;
    if (len <= 1) {
      return arr;
    }

    let pivot = arr[0];
    let lessThan = [];
    let greaterThan = [];

    for (let i = 1; i < len; i++) {
      if (arr[i] < pivot) {
        lessThan.push(arr[i]);
      } else {
        greaterThan.push(arr[i]);
      }
    }

    return [...quickSort(lessThan), pivot, ...quickSort(greaterThan)];
  };
console.log(quickSort([5, 1, 2, 6, 3, 17, 20, 19, 13, 15]))
// Result: [ 1, 2, 3, 5, 6, 13, 15, 17, 19, 20 ]

The code is available in the github gist: https://gist.github.com/Magesh-sam/24ed2283edeb5cb9126121a39d29a542

https://mageshkannan.vercel.app/