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 n2
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!)
🙏 THANK YOU FOR READING!
References:
School notes...
School books...
Khan academy
Please leave a comment, tell me about you, about your work, comment your thoughts, connect with me!
☕ SUPPORT ME AND KEEP ME FOCUSED!
Have a nice time hacking! 😊
Top comments (0)