Another way to implement Quick Sort in C

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 Flow

The general logic remains the same.

  1. We found a pivot item first (this time, we start from the left, or the smallest index)
  2. Expected outcome is put all elements smaller than pivot at the left, and those lager than pivot at its right
  3. Iterate index1 from the left, and compare the value to pivot. Exit iteration when the value is larger than pivot
  4. Iterate index2 from the right, and compart the value to pivot. Exit iteration when the value is smaller than pivot
  5. Swap the item at index1 and index2
  6. Repeat step 3 ~ 5 until index1 is larger than index2 (when both index cross each other, the entire array has been screened through)
  7. Swap the item at the last index1 with pivot
  8. 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)
  9. Recursion comes in the play: repeat step 1 ~ 7 to the left and right array respectively

Gist Example

Related Topics

Quick Sort explained in one minute

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Yu-Ming, CHANG (he/him)

Yu-Ming, CHANG (he/him)

I enjoy the positive mind flow when writing code to solve a problem. This is my journey to become a software developer