DEV Community

Cover image for QuickSort Algorithm in Javascript
Shubham Tiwari
Shubham Tiwari

Posted on • Updated on

QuickSort Algorithm in Javascript

Hello Everyone Today I am going to show you how to write QuickSort Algorithm in Javascript.

QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

Always pick first element as pivot.
Always pick last element as pivot (implemented below)
Pick a random element as pivot.
Pick median as pivot.
The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.

IQKUC SROT (1)

Here is The Code Part -

function QuickSort(Arr){
  if(Arr.length <= 1){
    return Arr;
  }

  const pivot = Arr[Arr.length - 1];
  const leftArr = [];
  const rightArr = [];

  for(let i=0; i < Arr.length-1;i++){
    Arr[i] < pivot ? leftArr.push(Arr[i]) :  rightArr.push(Arr[i])
  }

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

}

const items = [1,5,2,99,81,100,144,121,91,85,74,10];
console.log(QuickSort(items));
Enter fullscreen mode Exit fullscreen mode
  1. So, First we will check the length of the Array and if it is 1 then we will return the array as it is.
  2. Then we will select a pivot element which is last element in our case.
  3. Then we will create two empty arrays leftarr and rightarr to compare elements with pivot and place the element accodingly.
  4. Then we will iterate the array using for loop and inside for loop we will check each element that it is smaller than pivot or greater than pivot
  5. If the Element is smaller than pivot, then we will push it into left array and if the element is greater than pivot then we will push the element into right array.
  6. Then we will recursively call QuickSort for left and right array to partition the arrays until it get sorted completely.
Output - 
[1,2,5,10,74,81,85,91,99,100,121,144]
Enter fullscreen mode Exit fullscreen mode

I am New to Data Structures and Algorithm.So, if you find any mistake in this post please correct it in the comment section
THANK YOU

Instagram - https://instagram.com/w_a_a_d_u__h_e_c_k

Oldest comments (19)

Collapse
 
absphreak profile image
ᴀʙʜɪɴᴀᴠ sʜᴀʀᴍᴀ✩

Good use of destructuring with recursion.

Collapse
 
goodlifeinc profile image
DJango Freeman

maybe u meant spread with recursion :)

Collapse
 
owenmelbz profile image
Owen Melbourne

Maybe you meant spread with recursion? 🙂

Collapse
 
shubhamtiwari909 profile image
Shubham Tiwari

Yeah But Data Structure is important because Understanding the logic of One algorithm can help you to write more algorithms related to your problems

Collapse
 
ankittanna profile image
Ankit Tanna

That's a narrow minded thinking. If there are 100 thousand elements you would ha e to resort to a proper algorithm.

Collapse
 
owenmelbz profile image
Owen Melbourne

Tbf - Although I agree with you in "the real world" I read this as "How to create a quicksort algorithm using Javascript" - Which this article does.

It is not a "How to sort an array using Javascript" to which your comment is related.

Collapse
 
umar9780 profile image
محمد عمر

😂

Collapse
 
umar9780 profile image
محمد عمر

legand 😂

 
shubhamtiwari909 profile image
Shubham Tiwari

Brother its just a Simple Quick sort algorithm
Code for learning purpose
I didn't said it is better than sort method or any other sorting Algorithm
It is a just part of the DSA which I showed here and as I am learning Javascript also
So, for practice purpose I used Javascript to demonstrate the implementation of this Algorithm.

 
shubhamtiwari909 profile image
Shubham Tiwari

Yeah I also use Array.prototype.sort method and it is easy to use and good

Collapse
 
notruelimit profile image
Uros Mitrovic

You have an objectively better method, never reinvent the wheel

Collapse
 
hadihammurabi profile image
Hadi Hidayat Hammurabi

Yeesss... It is more quick i think 😄

Collapse
 
timothyokooboh profile image
timothyokooboh

This is by far the best implementation of quick sort (in terms of simplicity and comprehension) that I have seen. Thank you very much.

Collapse
 
shubhamtiwari909 profile image
Shubham Tiwari

Thank you sir

Collapse
 
rrdlpl profile image
R

isn't the point of quicksort that you don't need extra memory? left and rightArray aren't necessary imo.

Collapse
 
shubhamtiwari909 profile image
Shubham Tiwari

can you show this correction in code as i am not getting the point😆

Collapse
 
rrdlpl profile image
R

Sure,

class QuickSort {
  public sort(array: number[], left: number, right: number): number[] {
    if (array.length <= 1) {
      return array;
    }

    let index = this.partition(array, left, right);

    if (left < index - 1) {
      this.sort(array, left, index - 1);
    }

    if (index < right) {
      this.sort(array, index, right);
    }

    return array; 
  }
  private partition(array: number[], left: number, right: number): number {
    const pivot = array[Math.floor(right + left / 2)];
    let i = left;
    let j = right;


    while (i <= j) {
      while (array[i] < pivot) {
        i++;
      }
      while (array[j] > pivot) {
        j--;
      }

      if (i <= j) {
        this.swap(array, i, j);
        console.log(`swapping ${i} ${j}`, array);
        i++;
        j--;
      }
    }

    return i;
  }

  private swap(array: number[], i: number, j: number) {
    const aux = array[i];
    array[i] = array[j];
    array[j] = aux;
  }
}

const q = new QuickSort();
const array = [5, 6, 3, 7, 1, 8, 9];

console.log(q.sort(array, 0, array.length - 1));

Enter fullscreen mode Exit fullscreen mode
Thread Thread
 
shubhamtiwari909 profile image
Shubham Tiwari

So this one is memory efficient

Some comments may only be visible to logged-in visitors. Sign in to view all comments.