DEV Community

QuickSort Algorithm in Javascript

Shubham Tiwari on August 28, 2021

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 ...

Read full post

R • Sep 19 '22

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

Shubham Tiwari • Sep 19 '22

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

R • Sep 19 '22

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));

Shubham Tiwari • Sep 19 '22

So this one is memory efficient

Owen Melbourne • Aug 31 '21

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.

timothyokooboh • Aug 9 '22

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

Shubham Tiwari • Aug 9 '22

Thank you sir

ᴀʙʜɪɴᴀᴠ sʜᴀʀᴍᴀ✩ • Aug 28 '21

Good use of destructuring with recursion.

DJango Freeman • Aug 29 '21

maybe u meant spread with recursion :)

Owen Melbourne • Aug 31 '21

Maybe you meant spread with recursion? 🙂

Shubham Tiwari • Aug 29 '21

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

Shubham Tiwari • Sep 2 '21

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.