This series of articles is meant to help me pass those dreaded technical interviews. I’ll be covering in detail each and every algorithm that I find the time and motivation to learn about. I hope you find these articles helpful as well.

Many of these articles aren’t exactly finished. They’re meant to be a kind of running notebook that I update and refine continuously over time. If you find an algorithm isn’t well-explained or want some clarification on a subject, feel free to shoot me an email at m.d.demichele@gmail.com.

Feel free also to reach out and just say hey! If you’re a curious programmer like me, I’d love to hear from ya.

Returning back the subject of today’s article, let’s cover the quick sort algorithm.

# Quick Sort Algorithm

Quick Sort is a divide-and-conquer algorithm. The algorithm works by recursively breaking apart an array into smaller and smaller partitions, centered around a “pivot point.”

# Quick Sort Steps

- Choose an element to be the pivot
- Partition the array based on where the pivot is located. You’ll have a left partition that is less than the pivot and a right partition that is greater than the pivot.
- Recursively apply quick sort on left partition.
- Recursively apply quick sort to the right partition.

# Time Complexity

Quick sort can have a worst case time complexity of O(n^2). But if the pivot is chosen correctly, it can have an average time complexity of O(n log n).

# Space Complexity

Quick sort uses O(log n) memory.

# Example Implementation

I’ve provided an example implementation of quick sort down below. Like I’ve said in other algorithm articles, I hate reading through code I don’t really understand, so I’ll include a brief description of what’s going on in the future. For now, here’s the code.

# Source Code

To see a working implementation of quick sort, along with a couple of sample tests, check out my project at Quick Sort Algorithm Github

# Further Resources

Here’s a few helpful resources you might find useful.