Like most sorting algorithms, the Quick Sort algorithm sorts an array of items in ascending order. There are numerous approaches to Quick Sort. This article will focus on one method. This approach selects the left-most element of the array as the pivot. It then compares it against the last element in the array. If the pivot is less than the element it’s being compared to, that element becomes the pivot and the left side is incremented. If the pivot is greater than the element it’s being compared to, the index value of that element is incremented. This occurs until the left and the right sides meet. Once the values meet, the element where they met is said to be sorted. Left and right partitions are created, and new pivot points are generated.

This version of the Quick Sort algorithm will follow these rules:

This is only one way to do the Quick Sort algorithm. We’ll now move to an example.

 

The left element at index 0 is set as the pivot value and the right element is set as the last element in the array. The pivot value is compared to the right element. Since the right value is less than the pivot value, the right value is swapped with the pivot value, and the right value becomes the new pivot value; left index is incremented.

 

 

Next, the new pivot value is compared to the value at index 1. Since the pivot is greater than the left value, the pivot remains in the current position and the left element is incremented.

 

 

The Quick Sort algorithm compares pivot to left. Since the pivot value is not greater than the left value, the pivot value is swapped with the left value. Index 2 becomes the new pivot and the right index is decremented.

 

Next, the new pivot at index 2 is compared with the value at index 4. Since 5 is not less than 3, the values are swapped, and the left index value is incremented.

The Quick Sort algorithm compares the pivot value to the left value. Since the pivot value is larger than the left value, the left index is incremented.

 

 

Now, both the left and the right arrows point to the same element. The algorithm knows that this value is sorted. Left and right partitions are created.

 

 

The algorithm starts working on the left partition. The value at index 0 becomes the new pivot. The left arrow points to the pivot value and the right arrow points to the last element in the left partition.

 

 

The pivot value is compared to the right value. Since the pivot is larger than the right value, the two values are swapped. Index 3 becomes the new pivot and the left index value is incremented.

 

The algorithm compares the pivot value to the value at index 1. Since the pivot value is larger, the left index value is incremented.

 

 

The algorithm compares the pivot value to the value at index 2. Since the pivot value is larger, the left index value is incremented.

 

The left and right arrows have met at the same element. The Quick Sort algorithm now knows that the value at index 3 is sorted. New partitions are created. Since there is no unsorted value to the right of the pivot, only the left partition is created.

 

The algorithm starts working on the new left partition since it’s still within the old left partition. It assigns index 0 as the pivot value and points the left arrow to it. The right arrow points to the last element within the new left partition.

 

The algorithm starts by comparing the pivot value to the right value. Since the pivot value is less than the right value, the right index is decremented.

 

 

Next, the values at indices 0 and 1 are compared. Since the pivot value is smaller, the right value is decremented.

 

 

The left and right arrows have met at index 0. The Quick Sort algorithm knows that the value at index 0 is now sorted. New partitions are created. Since there is no value to the left of the pivot, only the right partition is created.

 

 

Since the algorithm is still within the left partition, it starts working on the new right partition. The pivot and the left arrow both point to index 1; the right arrow points to index 2.

 

 

The values at indices 1 and 2 are compared. Since the pivot value is less than the right value, the right index is decremented.

 

The left and right arrows have met at index 1. The algorithm knows that the value at index 1 is sorted. New partitions are created. Since there are no unsorted elements to the left of index 1 within this partition, only the right partition is created.

 

 

Since the Quick Sort algorithm is still within the first left partition, it starts working on the new right partition. It points the pivot, left arrow, and right arrow to index 2 since that is the only element in this partition.

 

The arrows have met at index 2, so the algorithm knows that the value at index 2 is now sorted.

 

The Quick Sort algorithm has finally made its way out of the first left partition and starts working on the right partition. It points the pivot, left arrow, and right arrow to the only element available.

 

Since both arrows point to the same element, the algorithm concludes that the value at index 5 is now sorted.

 

Since there are no other partitions to sort, the Quick Sort algorithm ends.

 

If you liked what you read, my book, An Illustrative Introduction to Algorithms, covers this Algorithm and many more.

 

My Book: An Illustrative Introduction to Algorithms

 

 

This book was written to fill the gap that exists when Computer Science students and programmers, attempt to learn and analyze the different algorithms that currently exist. I took a course on Algorithms and was disappointed in the type of material that’s currently available. There are two types of books that I kept running into:

First, the overly complex book. This book seems like it’s designed for people that are already fluent in the topics and wanted a more detailed and mathematical approach to algorithms.
Second, the overly simple book. A basic introduction to algorithms. This is a high-level overview of some algorithms, and most complex algorithms are not mentioned. After completion, the person is still incapable of showing how the algorithm runs when a problem is presented.
This book is designed for undergraduate upper-class students and programmers that want to expand their horizon. It can be used as a supplementary book alongside the complex book. Readers will gain the knowledge necessary to solve those mathematically intensive algorithmic problems that were presented in the complex book.Each chapter consists of a brief description of how the algorithm works followed by a detailed example or two. No steps are skipped during the traversal process. The reader is presented with a clear, simplified approach to solving the algorithm that the chapter is dedicated to.

Each chapter follows a natural progression from the previous chapter. If certain algorithms rely heavily on prior knowledge, the previous chapter covers that topic. For example, Kruskal’s algorithm relies heavily on prior knowledge of Minimum Spanning Trees and Greedy Algorithms. Each of those topics receives a chapter of its own.

Available now at Amazon.com