Another way to implement Quick Sort in C
Check out all articles in Technical Article Structure on Medium
My article last week explained how to implement quick sort by iterating the array from left to right. If you haven’t read it, here is the post: Quick Sort explained in one minute.
What I found interesting in programming is that, there are so many other ways to achieve the same result we expect. The purpose of this article is to demonstrate the diversity in programming. Another way to implement quick sort in C is to iterate and compare elements from both ends toward the middle point, and stops at the first time they cross each other.
Before we dive in, just to make it clear, I personally prefer the first way to implement quick sort because it is much easier to understand what’s going on behind the scene
The general logic remains the same.
- We found a pivot item first (this time, we start from the left, or the smallest index)
- Expected outcome is put all elements smaller than pivot at the left, and those lager than pivot at its right
- Iterate index1 from the left, and compare the value to pivot. Exit iteration when the value is larger than pivot
- Iterate index2 from the right, and compart the value to pivot. Exit iteration when the value is smaller than pivot
- Swap the item at index1 and index2
- Repeat step 3 ~ 5 until index1 is larger than index2 (when both index cross each other, the entire array has been screened through)
- Swap the item at the last index1 with pivot
- Now, every item at the left of pivot is smaller than pivot, and the rest at the right is larger than pivot (doesn’t mean there sorted)
- Recursion comes in the play: repeat step 1 ~ 7 to the left and right array respectively