An illustration with an example

In this algorithm, we partition an unsorted array into two sub-arrays, in such a way that all the elements on the left side of that partition point (also called a pivot) should be smaller than the pivot, and all the elements on the right side of the pivot should be greater. After the first iteration of the quick sort algorithm, the chosen pivot point is placed in the list at its correct position. After the first iteration, we obtain two unordered sub-lists, and follow the same process again on these two sub-lists. Thus, the quick sort algorithm partitions the list into two parts and recursively applies the quick sort algorithm on these two sub-lists to sort the whole list. 

We start by choosing a pivot point with which all the items are to be compared, and at the end of the first iteration, this value will be placed in its correct position in the ordered list. Next, we use two pointers, a left pointer, and a right pointer. The left pointer initially points to the value at index 1, and the right pointer points to the value at the last index. The main idea behind the quick sort algorithm is to move the items that are on the wrong side of the pivot value. So, we start with the left pointer, moving from in a left-to-right direction, until we reach a position where the item has a greater value than the pivot value. Similarly, we move the right pointer toward the left until we find a value less than a pivot value. Next, we swap these two values indicated by the left and right pointers. We repeat the same process until both pointers cross each other; in other words, when the right pointer index indicates a value less than that of the left pointer index.

Let's take an example of a list of numbers, {45, 23, 87, 12, 72, 4, 54, 32, 52}, to understand how the quick sort algorithm works. Let's assume that the pivot point in our list is the first element, 45. We move the left pointer from index 1 in a rightward direction, and stop when we reach the value 87, because (87>45). Next, we move the right pointer toward the left, and stop when we find the value 32, because (32<45)

Now, we swap these two values, as shown in the following diagram:

After that, we repeat the same process and move the left pointer toward the right direction, and stop when we find the value 72, because (72>45). Next, we move the right pointer toward the left and stop when we reach the value 4, because (4<45). Now, we swap these two values, because they are in the wrong direction of the pivot value. We repeat the same process and stop once the right pointer index value becomes less than the left pointer index. Here, we find 4 as the splitting point, and swap it with the pivot value. This is shown in the following diagram:

It can be observed that after the first iteration of the quick sort algorithm, the pivot value 45 is placed at its correct position in the list.

Now we have two sub-lists:

  1. The sub-list to the left of the pivot value, 45, has values of less than 45.
  2. Another sub-list to the right of the pivot value contains values greater than 45. We will apply the quick sort algorithm recursively on these two sub-lists, and repeat it until the whole list is sorted.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset