QuickSort is one of the most powerful and widely-used sorting algorithms. In this article, we go far beyond the basics — exploring not just how it works, but how to visually animate it using Flutter with CustomPainter and AnimationController.
1. What Is QuickSort?
QuickSort is a recursive divide-and-conquer algorithm that sorts elements by choosing a pivot and partitioning the array around it. It is often preferred due to its in-place sorting nature and excellent average-case performance.
Core Idea
1. Choose a Pivot
Pick an element from the array. This is called the pivot.
Common strategies:
- First element
- Last element
- Middle element
- Random element
2. Partition the Array
Rearrange elements so:
- Elements less than pivot come before it
- Elements greater than pivot come after it
3. Recursively Apply
Apply the same logic to the left and right subarrays.
[9, 3, 7, 1, 6] using pivot 6Partition →
[3, 1] | 6 | [9, 7]Recursively sort both sides.
2. Step-by-Step QuickSort Example
Let’s walk through QuickSort step by step on the array:
Initial array: [5, 3, 8, 4, 2]Step 1: First QuickSort Call
Call: quickSort(arr, 0, 4)
- Choose pivot = 2 (last element)
- Partitioning: move all elements < 2 to the left
- No elements are less than 2 → array remains
- Swap pivot with first element:
[2, 3, 8, 4, 5]
Pivot index = 0. Now QuickSort two subarrays:
Left: [] (empty) → done
Right: [3, 8, 4, 5] → continueStep 2: QuickSort on Right Half
Call: quickSort(arr, 1, 4)
- Pivot = 5
- Compare 3: < 5 → move to left
- Compare 8: > 5 → stay
- Compare 4: < 5 → move left
- Array becomes:
[2, 3, 4, 8, 5] - Swap pivot (5) with correct index:
[2, 3, 4, 5, 8]
Pivot index = 3. New recursive calls:
Left: [3, 4]
Right: [8]Step 3: Sort [3, 4]
Call: quickSort(arr, 1, 2)
- Pivot = 4
- Compare 3: < 4 → move to left
- Swap pivot with itself: unchanged
Sorted: [2, 3, 4, 5, 8]Final Array:
[2, 3, 4, 5, 8]QuickSort completed with in-place operations and no extra memory.
3. Pivot Strategies Compared
| Strategy | Description | Performance |
|---|---|---|
| First element | Choose first item as pivot | Bad for sorted data |
| Last element | Choose last item | Also vulnerable to sorted input |
| Random | Randomly pick pivot | Best average performance |
| Median-of-three | Median of first, middle, last | Improved consistency |
4. 🔬 Mathematical Recursion Model
QuickSort’s recurrence relation (for expected case) is:
T(n) = T(k) + T(n - k - 1) + Θ(n)
Where:
kis the number of items less than the pivotΘ(n)is the partitioning time
Best Case (Balanced Partition)
T(n) = 2T(n/2) + Θ(n) → O(n log n)Worst Case (Unbalanced)
T(n) = T(n-1) + Θ(n) → O(n²)5. Flutter Implementation Highlights
Data Structures
List<int> _array: the array being sortedList<SortStep> _steps: a recorded sequence of changesCustomPainter: renders bars based on array state
🔁 QuickSort Logic
Future _quickSort(int low, int high) async {
if (low < high) {
int pi = await _partition(low, high);
await _quickSort(low, pi - 1);
await _quickSort(pi + 1, high);
}
} Partition Function
Future<int> _partition(int low, int high) async {
int pivot = _array[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (_array[j] <= pivot) {
i++;
_swap(i, j);
_recordStep(i, j);
}
}
_swap(i + 1, high);
_recordStep(i + 1, high);
return i + 1;
}Painting State
normal bar: bluepivot: redcomparing/swapping: green or yellow
6. Animation Engine in Flutter
Animations are triggered using a Timer.periodic that advances through the _steps list.
Timer.periodic(const Duration(milliseconds: 300), (timer) {
if (_currentStepIndex < _steps.length) {
setState(() {
_applyStep(_steps[_currentStepIndex++]);
});
} else {
timer.cancel();
}
});📉 Performance Considerations
- Bar rendering tied to frame rate (~60fps)
- Memory-efficient since QuickSort is in-place
- Heavy recursive calls = deeper stack, but manageable
7. QuickSort vs Other Algorithms
| Algorithm | Avg Time | Space | Stable |
|---|---|---|---|
| QuickSort | O(n log n) | O(log n) | No |
| MergeSort | O(n log n) | O(n) | Yes |
| HeapSort | O(n log n) | O(1) | No |
8. Final Thoughts
QuickSort remains one of the most elegant algorithms for sorting — its divide-and-conquer nature, average-case speed, and in-place optimization make it ideal for both theory and production.
Visualizing it in Flutter brings the algorithm to life, offering a powerful way to teach, debug, and experiment. With CustomPaint and animations, you can explore the recursive tree, pivot influence, and partitioning dynamics frame by frame.
Want to go deeper? Try:
- Adding visual call-stack lines on each recursion
- Tracking total swaps and comparisons
- Comparing animations of different pivot strategies side-by-side
Up Next: Bubble Sort Visualization & Analysis
While simple, Bubble Sort helps demonstrate algorithmic basics and animation flow. Stay tuned!
