DATA STRUCTURE AND ALGORITHM
QUICK SORT ALGORITHM
PRESENTED BY: RON JOSEPH R. ALCANTARA
WHAT IS QUICK SORT ALGORITHM?
WHAT IS QUICK SORT ALGORITHM?
Quick Sort is a widely-used, efficient sorting algorithm based on the Divide and
Conquer paradigm. Invented by Tony Hoare in 1960, it is particularly appreciated for
its average-case time complexity of O(nlogn). Quick Sort operates by selecting a
pivot element, partitioning the array into two sub-arrays around the pivot, and then
recursively sorting these sub-arrays.
KEY CONCEPTS OF QUICK SORT ALGORITHM?
Quick sort algorithm is a recursive algorithm
Quick sort = pivot (is one of them items in the array that meets the three following
conditions after its sorted.)
1. Correct position in final, sorted way
2. Items to the left are smaller
3. Items to the right are larger
HOW DOES QUICK SORT WORKS?
Example:
The first step in quick sort is to choose a pivot
In this example we take 3 as our pivot
We move the pivot to the ending array, to get it out of our way
Next step is we are going to look for two items
Lets swap the item form the left to the item from the right
We repeat the process, 5 is the item from left and 0 is item from right
Again, we swap 5 and 0
Item from left has a greater index than item from right
We swap item from left with our pivot
3, our pivot is now in our correct spot
Because quick sort is recursive, we repeat the process with the larger partition that
we made
We’ll choose 7 as our pivot and move it in the end
We repeat the same process
We repeat the same process
We repeat the same process
We now have 3 and 7 in their correct positions
Because Quict Sort is a recursion algorithm, we will repeat the same process
HOW TO CHOOSE THE PIVOT?
HOW TO CHOOSE THE PIVOT?
A popular method is called the “median-of-three”
It is a method where we look at the first, middle, and last elements of the array
We sort them properly and choose the middle item as our pivot
PSEUDOCODE FOR QUICKSORT
CONCLUSION
CONCLUSION
Quick Sort is an efficient and widely used algorithm with a well-balanced tradeoff
between complexity and performance. While Quick Sort is not stable and may have
limitations in scenarios requiring guaranteed efficiency for all input types, strategies
like random pivot selection or hybrid methods (e.g., Introsort) help mitigate these
drawbacks. Overall, Quick Sort remains one of the most widely used sorting
algorithms due to its balance of speed, memory efficiency, and implementation
simplicity.
SOURCE
THANK YOU!
