Table Of Contents
* 🤓 INTRODUCTION
* 👉🏻 ABOUT QUICK SORT ALGORITHM
* 👨🏻‍🏫 EXPLANATION
* 🖖🏻 PESUDO CODE
* 🛠 IMPLEMENTATION
* 👩🏻‍💻 CODE
* 🤔 COMPLEXITY
* 🙏 THANK YOU

🤓 INTRODUCTION

Top of the day, my dear coders! I hope you are all having a beautiful weekend. Welcome to another chapter of the Sorting algorithms with JavaScript series. Today we are talking about the QuickSort algorithm!

Connect with me via Twitter or LinkedIn

⚡⚡⚡ EDUCATION TIME!

Since the beginning of this series, we are talking about various algorithms. We should in my opinion mention the Algorithm as a term or idea.

An algorithm in computer science as well as in mathematics is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation.

Algorithms are always unambiguous and are used to perform the following tasks:

Calculations
Data processing
Automated reasoning And much, much more.

Important thing is that an algorithm, an effective algorithm, can be expressed within a finite amount of space and time.

The concept of the algorithm has existed since antiquity. Division algorithm and an arithmetic algorithm was used by ancient Babylonian mathematicians c.2500 BC and Egyptian mathematicians c. 1550 BC.

The word 'algorithm' has its roots in Latinizing the nisba, indicating his geographic origin, of the name of Persian mathematician Muhammad ibn Musa al-Khwarizmi to "algorismus".

Algorism is the art by which at present we use those Indian figures, which number two times five. - Alexandre de Villedieu

👉🏻 ABOUT QUICK SORT ALGORITHM

Quicksort is an efficient sorting algorithm. His father is a British computer scientist Tony Hoare, not the gentleman in the following gif as one might think.

The quicksort algorithm is a divide-and-conquer algorithm, an algorithm that recursively breaks down a problem into two or more subproblems of the same or related type until these become simple enough to be solved directly.

In the quicksort algorithm, all the real work happens in the divide step of the divide-and-conquer paradigm.

👨🏻‍🏫 EXPLANATION

We are dividing our sorting problem into three steps: divide, conquer, combine.

Let's take a typical subarray A[p...r]

DIVIDE: Partitioning (rearrange) the array A[p...r] into two (possibly empty) subarrays A[p...q-1] and A[q+1...r] such that each element of A[p...q-1] is less than or equal to A[q], which is, in turn, less than or equal to each element of A[q+1...r]. We are computing the index q as part of this partitioning procedure.

CONQUER: Sort the two subarrays A[p...q-1] and A[q+1...r] by recursive calls to quicksort.

COMBINE: Because the subarrays are already sorted, no work is needed to combine them: the entire array A[p...r] is now sorted.

🖖🏻 PSEUDO CODE

QUICKSORT(A: array, p, r)
1  if p < r
2    q = PARTITION(A,p,r)
3    QUICKSORT(A,p,q-1)
4    QUICKSORT(A,q+1,r)

PARTITION(A: array, p, r)
1  x = A[r]
2  i = p - 1
3  for j = p to r-1
4    if A[j] <= x
5      i = i + 1
6      swap A[i] with A[j]
7  swap A[i+1] with A[r]
8  return i+1

🛠 IMPLEMENTATION

👨🏻‍💻 CODE

Play with code! 🚀

🤔 COMPLEXITY

Worst case: It occurs when the partitioning routine produces one subproblem with n-1 elements and one with 0 elements. If the partitioning is maximally unbalanced at every recursive level of the algorithm, the running time is Big O of n²

Best case: In the most even possible split, Partition function will produce two subproblems, each of size more than n/2, since one if of size [n/2] and one of size [n/2]-1; In this case, complexity is Big O of nlogn (Pretty good!)