## Sorting (Part 6.0): Quick Sort [Sorta Efficient]

Greetings, fellow NBers!

Welcome to my sixth iteration of my sorting series. Today, we'll be discussing a personal favorite: Quicksort, or Quick Sort.

## Quick Sort: The Algorithm Under the Hood

Quick Sort is what's called a "divide and conquer" sorting algorithm. It takes a particular approach: pick an element **p** from the array-to-sort **arr**, any element, and call that the pivot point. Put all the elements in **arr** that are less than **p** on the left side of **p**, so in **arr[0]** to **arr[k-1]**, where **k** is the final position in the sorted array of **p**. Put all the elements greater than **p** on the right of **p**, or in the spots **arr[k+1]** to **arr[n-1]**, where **n** is the size of the array.

There are a few ways to accomplish this -- some are more efficient than others. Today, I'll be showing you the easiest way to do it, where we make new arrays for the "left" and "right" parts, and then join them at the end, rather than doing what's called in-place quicksort.

## Time Complexity

Mathematically, the worst-case time complexity of Quick Sort is **O(n^2)**, when the array-to-sort is in the worst possible order: reversed.

**BUT**, Quick Sort often behaves logarithmic-ally, rather than quadratic-ally, meaning it commonly has the time complexity **O(n * log(base 2) of n)**.

So, it is *sometimes* faster than the previously-covered bubble, insertion, and selection sorts... Don't get too excited, but insertion sort is coming back for a little cameo in a coming post...

*Image via staticflickr.com*

## Ruby Implementation

Here is the pastebin link; screenshots:

Okay, so our **quicksort(...)** function starts on line 6. The first thing you see is our declaration of **strlen**. On line 10, we check if **str**, our array-to-sort, is empty or only has one element. An array with one or fewer elements is always sorted, so we just return the original array.

On line 13, we hold the value of our pivot in **pivot_char** by accessing the value stored at index **pivot_point** in **str**. This **pivot_point** is chosen by the caller of **quicksort(...)**. I call the function on line 52 -- you won't see this line in the screenshots because it's just I/O -- and pass **rand(str.length)** for the value of **pivot_point**, basically telling **quicksort(...)** to use a random pivot. **Note:** often, you'll see implementations use different methods to pick out the pivot points, opting for the first or last element, or some other element entirely.

We then declare **left = []** and **right = []** to hold the values less than the pivot and greater than the pivot, respectively.

In the **for** loop on line 24 we go through **str** and put each element in either the **left** or **right** arrays, but never both, excluding the pivot, because we don't need to re-sort the pivot; it will be in its final position.

But we're not done yet. We now, on lines 37 and 38, take the newly filled (or not filled) **left** and **right** and call **quicksort(...)** on them, too. **Note:** this calling of a function from within itself is known as recursion. Make sure you have a terminator (ours is line 10) so that your function doesn't keep calling itself forever.

After the **left** and **right** arrays are quickly sorted -- pun intended -- we can stitch them together, the pivot in between, to build the completed, sorted **str**. We do this on lines 41 and 42, erasing **str** and then copying **left**, **pivot_char**, and **right** into a newly-emptied **str**.

On line 44, we flatten **str** before returning it because pushing **left**/**right** to **str** creates a 2D array, something we do not desire.

## C++ Version

Here you'll find the pastebin link; the screenshot is below:

As usual, I chose to use **vec** in place of **str**. Other than that, there is only one major contrast from the Ruby version: Before calling **quicksort(...)**, I check if the array-to-sort is empty. This is because of how C++ does random numbers. If I pick a random pivot in for an empty array, passing a random pivot would look like **rand() % 0**, because the size of an empty array is 0, yet you cannot do a modulo of 0, because you cannot divide by 0.

## Conclusion

If you noticed in the title, this article is *Part 6.0* that ".0" is there because I am implying the coming of a *6.1* and maybe even *6.2*.

Why? Because this method of quicksorting is resource-inefficient. I only showed you it because it's the easiest form of quicksort to understand and implement.

So, stay tuned for *Sorting (Part 6.1): Quick Sort [In-Place]*.

Happy Hacking,

oaktree

## Be the First to Comment

## Share Your Thoughts