Quick Sort Example | Step by Step with Figures

Assume A is a list of n data objects for the example of the QuickSort algorithm with step-by-step figures. The procedure of rearranging the elements such that they are in some logical order, such as numerically sorted when 'A' includes numerical data or alphabetically arranged when 'A' contains character data, is referred to as "sorting A." In this post, we will just look at one sorting method, quicksort.

Quicksort is a form of the divide-and-conquer algorithm. That is, the challenge of sorting a set is simplified to sorting two smaller sets. We provide a specific example to demonstrate this "reducing state/step." The reducing states are the steps of the quick sort algorithm.

Now, assume 'A' has 12 numbers and they are,

Fig. 01: A data array with n items 'A'

The quicksort algorithm's reduction state determines the ultimate position of one of the numbers; in our example, we will use the first number, 45. This is performed in the following manner. Starting with the last number, 67, scan the list from right to left, comparing each number to 45 and ending at the first number less than 45, which is 23. To get the list, replace 45 and 23.

Fig. 02: Interchanging for 45 and 23

Beginning with 23, scan the list from left to right in a reverse manner, comparing each number with 45 and pausing at the first number larger than 45. The answer is 56. Replace 45and 56 and the obtain list is,

Fig. 03: Interchange of 45 and 56

Starting with 56 this time, scan the list in the other manner, from right to left, until you reach the first number less than 45. It is 41. To get the list, exchange 45 and 41.

Fig. 04: Interchange of 41 and 45

Starting with 41. From left to right, go through the list. 78 is the first number that is bigger than 45. To get the list, replace 45 and 78.

Fig. 05: Interchange of 45 and 78

(Once again, all of the numbers to the left of 45 are less than 45.) Scanning the list from right to left, starting with 78, look for a number less than 45. We don't see such a number before 45. This signifies that every number has been scanned and compared to 45. Furthermore, as seen below, all numbers less than 45 now form the sublist to the left of 45, while all numbers larger than 45 now constitute the sublist to the right of 45:

Fig. 06: First sublist and second sublist

Thus, 45 is appropriately placed in its final position, and the process of sorting the entire list 'A' has been reduced to the task of sorting each of the sublists mentioned above figure with details. The reduction state described above is repeated for each sublist having two or more components. We must be able to maintain a record of certain sublists for future processing because we can only process one sublist at a time. This is performed by temporarily combining two stacks termed LOWER and UPPER.

The lower and upper stacks are more likely the left and right sides of the quicksort algorithm. We can proceed with the reduction process using lower and upper stacks. The first sublist will reserve on the stack and we will do the pushing and popping elements one by one.

Fig. 07: The array items with locations

A simple introduction of stacking process for the quicksort

<---- start of stacking process introduction ---->

For this the location of the items to be considered instead of value for the stacking process. This can like the below,

LOWER: 1 (beginning a1 item location)

UPPER: 12 (ending a12 item location)

To apply the reduction state, we have to empty the stack again and again.

LOWER: empty

UPPER: empty

then, insert the first sublist and second sublist locations,

LOWER: 1, 6 (beginning of the first second sublist items location)

UPPER: 4, 12 (ending of the first second sublist items location)

<---- End of stacking process introduction ---->

Whatever, we have to proceed with the first and second sublist continuously according to the steps of the quick sort algorithm which is done above with details.

The first sublist will be sorted faster than the second sublist because the length of the first sublist is a small value. The first sublist sorted way will be like this,

Fig. 08: Sorting the First sublist step 1

Fig. 09: Sorting the First sublist step 2

Fig. 10: Sorted First sublist

Then we will sort the second sublist. As the sublist is a longer length, then the quick sort algorithm will make another sublist which will be called a 'sub-sublist'.