Tony Hoare came up with DSA Quicksort in 1959. It is a “Divide and Conquer” algorithm that has worked for a long time. Algorithms like Bubble Sort are good for teaching logic, while Quicksort is made to work fast.
DSA Quicksort Overview
Quicksort is a very fast way to sort things that uses a recursive method. It operates by choosing a “pivot” element from the array and splitting the other elements into two sub-arrays based on whether they are smaller or larger than the pivot.
The Divide and Conquer Strategy
- Divide: Choose a pivot element and split the array so that elements smaller than the pivot go to the left and elements larger than the pivot go to the right.
- Conquer: Do the same thing again and again to the left and right sub-arrays.
- Combine: There is no need for a separate “merging” phase because the sub-arrays are already sorted.
How Does Quicksort Work?
The Partitioning stage is what makes Quicksort work. Depending on how it is set up, the “pivot” can be different:
- Pick the first element as the pivot.
- Pick the last element as the pivot.
- Pick a random element as the pivot (Recommended for avoiding worst-case).
- Pick the median element as the pivot.
Step-by-Step Visualization of Quicksort
Let’s sort the array: [10, 80, 30, 90, 40, 50, 70] using the last element (70) as the pivot.
- Initial Partitioning:
- Compare 10 with 70. 10 < 70 (Keep it left).
- Compare 80 with 70. 80 > 70 (Move it right).
- Compare 30 with 70. 30 < 70 (Keep it left).
- Compare 90 with 70. 90 > 70 (Move it right).
- Compare 40 with 70. 40 < 70 (Keep it left).
- Compare 50 with 70. 50 < 70 (Keep it left).
- After First Pass: The array looks like [10, 30, 40, 50, 70, 90, 80].
- The pivot 70 is now in its correctly sorted position.
- Recursion: Now, apply Quicksort to the left sub-array [10, 30, 40, 50] and the right sub-array [90, 80].
- Completion: The process continues until sub-arrays have only one or zero elements.
Quicksort in Python
Python’s clean syntax makes it easy to visualize the recursive nature of DSA Quicksort.
Python
def quicksort(arr):
if len(arr) <= 1:
return arr
else:
# Picking the middle element as pivot
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
# Usage
data = [33, 10, 55, 71, 29, 1, 99, 5]
sorted_data = quicksort(data)
print(f”Sorted Array: {sorted_data}“)
Note: While the above “list comprehension” method is easy to read, professional implementations often use “In-place Partitioning” to save memory.
Also Read :
- Sorting Algorithms : A Beginner’s Guide
- What Is Sorting In Data Structure, And Its Types?
- Advance Data Structure and Algorithms
- String in Data Structure
- Data Structures and Algorithms Quiz DSA MCQ Online
- Top 100 DSA Interview Questions
- DSA Python Libraries
- Divide and Conquer Algorithm: Definition, Examples & Time Complexity
DSA Quicksort At a Glance
Quicksort is known for its incredible speed, but it has a “weakness” depending on the pivot choice.
|
Case |
Time Complexity | When does it happen? |
|
Best Case |
O(n log n) |
The pivot always divides the array into two equal halves. |
| Average Case | O(n log n) | This is the standard performance in 99% of real-world scenarios. |
|
Worst Case |
O(n²) |
Happens when the pivot is always the smallest or largest element (e.g., sorting a already sorted array). |
| Space Complexity | O(log n) |
Due to the recursive stack. It is much more memory-efficient than Merge Sort. |
Comparison: Quicksort and Merge Sort
Why do developers often prefer Quicksort over Merge Sort? Here are the few differences:
|
Feature |
Quicksort | Merge Sort |
|
Strategy |
Divide and Conquer | Divide and Conquer |
| Extra Space | Very little (O(log n)) |
Significant (O(n)) |
|
Stability |
Not Stable | Stable |
| Best For | Arrays / Memory-limited systems |
Linked Lists / External Sorting |
| Cache Friendly | High (Contiguous access) |
Low |
DSA Quicksort Applications
Here the real life applications of DSA Quicksort:
- Commercial Databases: Most SQL databases use Quicksort (or a variant called Introsort) to handle ORDER BY queries.
- Operating Systems: The qsort() method in C and the sort() utilities in many libraries are better variants of Quicksort.
- Big Data Analytics: Quicksort is used to sort unstructured logs in the early phases of data cleansing so that they can be processed faster.
Game Development: Quicksort is typically used to sort items by how far away they are from the camera (Z-sorting) because it is fast and doesn’t take up much memory.
FAQs
Is Quicksort stable?
No. A stable sort keeps the order of equal elements the same. Quicksort can switch equal elements on either side of the pivot, which changes their order. Use Merge Sort if you need something that will stay the same.
Why is it quicker than Merge Sort if both have a time complexity of O(n log n)?
Quicksort has a smaller "hidden constant." Because it works in-place and is "cache-friendly" (accessing memory addresses that are close to each other), it generally outperforms Merge Sort on physical hardware.
How can I stay away from the O(n²) Worst Case?
Use the Median-of-Three rule (look at the first, middle, and last elements and pick their median as the pivot) or always choose a Random Pivot. This means that it is statistically impossible to hit the worst-case situation using real data.
Can Quicksort be used for Linked Lists?
Yes, but it is less efficient. Since Linked Lists don't allow random access to elements, picking a pivot in the middle or end requires O(n) traversal. Merge Sort is the preferred choice for Linked Lists.
What does it mean to sort "in place"?
It indicates that the algorithm sorts the data by moving things around in the original array, which only needs a little extra memory for the pivot and recursion stack.