Quicksort
About this app
Quicksort step by step — follow pivot choice, partitioning and swap operations interactively.
How Quicksort sorts
Quicksort is a divide-and-conquer algorithm. It picks a pivot from a section of the array, here the last element as in the Lomuto partition scheme. A pointer walks through the section, compares each element with the pivot and swaps smaller or equal values to the front. Finally the pivot moves between the two parts and sits at its final position. The same procedure then runs recursively on the left and the right part. On average Quicksort needs O(n log n) comparisons; in the worst case, for example already sorted data with this pivot choice, it needs O(n²).
What the app shows
Every step appears as its own row: pivot choice, comparison, swap and placement. Colours distinguish the pivot, the element being compared, the two partitions and the region that is already in its final sorted place. A coloured bar at the edge shows the recursion depth and a counter shows where you are. You can see that a placed pivot is never touched again.
Try it yourself
Enter your own numbers (2 to 16 values) or shuffle a random array. Use Forward and Back to go through the partitioning one step at a time, jump to the start or the end, or let the steps play automatically at an adjustable speed. Try an array that is already sorted and count how many steps it takes.
Frequently asked questions
- What is the pivot in Quicksort?
- The pivot is the value a section is split around: smaller or equal elements go to the left, larger ones to the right. After partitioning, the pivot is at its final position in the sorted array. In the Lomuto scheme the pivot is the last element of the section.
- What is the time complexity of Quicksort?
- O(n log n) on average, because the pivot usually splits a section roughly in half and the recursion is about log n levels deep. O(n²) in the worst case: if the pivot is always the largest or smallest element, as with a sorted array and the last element as pivot, each section only shrinks by one.
- Is Quicksort stable?
- No. Swapping can change the original order of equal values. In exchange Quicksort sorts in place and needs no extra memory apart from the recursion stack.
- What can I do in the Quicksort app?
- You enter your own numbers or shuffle, step through every comparison and swap, go back, or let it play. Colours mark the pivot, the comparison, the partitions and the sorted region, and a bar shows the recursion depth.
Subject: Computer science
More from Computer science
- Ackermann function
- Elevator simulator
- Binary workshop
- Binary versus linear search
- The Collatz problem
- Inside a CPU
- Swap the inside
- One frame in 16 milliseconds — how a game engine renders an image (3D)
A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps