```
⚡ QUICK SORT VISUALIZER
Choose Pivot • Partition • Compare • Swap • Recursively Sort
```
```
📥 Enter Your Data
```
```
📊 Current Array
Enter values and press START QUICK SORT.
```
```
```
📈 Live Statistics
Recursion Level
0
Comparisons
0
Swaps
0
Partitions
0
Steps
0
```
🔀 Partition Visualization
```
```
```
📝 Step-by-Step Explanation
1
Quick Sort selects a
pivot and rearranges the
elements so that smaller values go to the
left and larger values go to the right.
```
🧮 Quick Sort Mathematics
Choose a pivot:
pivot = A[high]
Start:
i = low − 1
For every element A[j]:
If A[j] ≤ pivot
then:
i = i + 1
and swap:
A[i] ↔ A[j]
Finally:
A[i+1] ↔ A[high]
The pivot is now in its correct position.
```
pivot = A[high]
Start:
i = low − 1
For every element A[j]:
If A[j] ≤ pivot
then:
i = i + 1
and swap:
A[i] ↔ A[j]
Finally:
A[i+1] ↔ A[high]
The pivot is now in its correct position.
```
🔢 Complete Mathematical Example
Initial Array:
10, 7, 8, 9, 1, 5
Choose last element as pivot:
pivot = 5
Start:
i = −1
Compare 10 with 5:
10 ≤ 5 → False
No swap.
Compare 7 with 5:
7 ≤ 5 → False
No swap.
Compare 8 with 5:
8 ≤ 5 → False
No swap.
Compare 9 with 5:
9 ≤ 5 → False
No swap.
Compare 1 with 5:
1 ≤ 5 → True
i = 0
Swap A[0] and A[4]:
1, 7, 8, 9, 10, 5
Finally swap pivot 5 with A[1]:
1, 5, 8, 9, 10, 7
Pivot 5 is now in its final position.
Left partition:
[1]
Right partition:
[8,9,10,7]
Quick Sort recursively processes both partitions.
```
10, 7, 8, 9, 1, 5
Choose last element as pivot:
pivot = 5
Start:
i = −1
Compare 10 with 5:
10 ≤ 5 → False
No swap.
Compare 7 with 5:
7 ≤ 5 → False
No swap.
Compare 8 with 5:
8 ≤ 5 → False
No swap.
Compare 9 with 5:
9 ≤ 5 → False
No swap.
Compare 1 with 5:
1 ≤ 5 → True
i = 0
Swap A[0] and A[4]:
1, 7, 8, 9, 10, 5
Finally swap pivot 5 with A[1]:
1, 5, 8, 9, 10, 7
Pivot 5 is now in its final position.
Left partition:
[1]
Right partition:
[8,9,10,7]
Quick Sort recursively processes both partitions.
```
```
⚙️ How Quick Sort Works
1
Choose a Pivot:
Select one element as the pivot.
This visualizer uses the last element.
2
Partition:
Move elements smaller than or equal to the pivot
toward the left side.
3
Move larger elements toward the right side.
4
Place the pivot between the two partitions.
5
Recursively apply Quick Sort to the left partition.
6
Recursively apply Quick Sort to the right partition.
```
```
⚖️ Advantages & Disadvantages
+
Advantages
• Very fast on average.
• Average time complexity is O(n log n).
• Can be implemented in-place.
• Usually performs well in practical applications.
• Very fast on average.
• Average time complexity is O(n log n).
• Can be implemented in-place.
• Usually performs well in practical applications.
−
Disadvantages
• Poor pivot selection can produce O(n²) time.
• Standard Quick Sort is not stable.
• Recursive implementation requires stack space.
• Poor pivot selection can produce O(n²) time.
• Standard Quick Sort is not stable.
• Recursive implementation requires stack space.
```
```
⏱️ Time & Space Complexity
Best Case
O(n log n)
Average Case
O(n log n)
Worst Case
O(n²)
Average Space
O(log n)
```
🎯 Pivot Concept
A good pivot divides the array into two
approximately equal parts.
Example:
[2, 4, 5] | 6 | [7, 8, 9]
This produces approximately balanced partitions and gives:
O(n log n) average performance.
A poor pivot may produce:
[] | 1 | [2,3,4,5,6,7]
Repeated poor partitions can lead to:
O(n²)
```
Example:
[2, 4, 5] | 6 | [7, 8, 9]
This produces approximately balanced partitions and gives:
O(n log n) average performance.
A poor pivot may produce:
[] | 1 | [2,3,4,5,6,7]
Repeated poor partitions can lead to:
O(n²)
No comments:
Post a Comment