Hello, curious learner! You've made it more than halfway through our learning path, and today, we will embark on a journey through the Quick Sort world. Picture yourself organizing various items — like toys or books — by size or color. That's what Quick Sort does with spectacular speed. Are you ready to explore further? Fantastic! Let's get started.
Quick Sort is a clever little algorithm invented by a British computer scientist named Tony Hoare in 1959. It uses a strategy called divide-and-conquer to put elements in order. Quick Sort takes an array, selects a particular "pivot" element, and then places everything smaller than the pivot on one side and everything larger on the other.
Quick Sort has a three-step process:
- Pick a random "pivot" element from the array.
- Move all elements smaller than the pivot to one side and bigger ones to the other. This operation effectively divides the array into two parts, guaranteeing that all the elements will be kept within their part until the end of the sorting process.
- Repeat steps 1 and 2 for each part until there are no more unsorted elements.
For example, let's say we have nine marbles with numbers: [3, 9, 4, 7, 5, 1, 6, 2, 8]
.
We choose a marble, called the pivot, to help us sort the others. For this example, let's pick 7
as the pivot.
After the first round of sorting, we rearrange the marbles so that all marbles smaller than 7 are on the left, and all marbles larger than 7 are on the right.
The result would look like this: [3, 4, 5, 1, 6, 2, 7, 9, 8]
.
