You will be asked to specify how many numbers you require to be sorted. Suppose we want to sort 8 numbers; the value 8 entered by the user will be assigned to the len variable. A for loop is executed enabling us to enter the number to be sorted. The values we enter will be assigned to the arr array as shown in Figure 9.21.
Two variables, lindex and uindex, are initialized to represent the desired first and last index of the array, that is 0 and 7, respectively. The lindex and uindex locations are supposed to keep the smallest and largest values in the array. The values of lindex and uindex, that is, 0 and 7, will be pushed to the stack. In the pushstk1 function, the value of the top index, whose default value is -1, is incremented to 0 and the value of lindex is assigned to the stack1 array at the [0] index location. Similarly, in the pushstk2 function, the value of the top2 index is also incremented to 0, and the value of uindex is assigned to the stack2 array at the [0] location.
A while loop is set to execute for as long as the value of top1 is not equal to 1. That means, until stack1 is empty, the program will keep executing. Within the while loop, the values pushed in stack1 and stack2 are popped and assigned to the two variables of sindex and eindex, respectively. These variables represent the starting and ending index locations of the array or the part of the array that we want to sort using quick sort.
stack1 and stack2 contain the values of 0 and 7, respectively, which are popped and assigned to sindex and eindex, respectively. The quick function is invoked and the values in sindex and eindex are passed to an argument. In the quick functions, the values of sindex and eindex arguments are assigned to the two parameters of si and ei, respectively.
Within the quick function, the value of si, that is 0, is assigned to another variable, li. A while loop is executed in an infinite loop. Within the while loop, another while loop is set to execute that will make ei move toward the left, that is, it will make the value of ei decrement until the element at the arr[ei] location is greater than the arr[li] location:
Because arr[ei] < arr[si], interchanging of their values will take place (see Figure 9.22(a)). After interchanging the values at arr[ei] and arr[si], the arr array will appear as shown in Figure 9.22(b):
After interchanging of values, the index location number of ei, that is 7, will be assigned to li. Another while loop is set to execute while arr[si] is smaller than arr[li], where li represents the ei index currently; and within the while loop, the location of the si index pointer is incremented. That is, the si index pointer is moved right to arr[si] < arr[li]:
Now, the following things will happen:
- Because arr[si] < arr[ei] (that is, 4 < 6), si will move right by one location to arr[1]
- Because arr[si] < arr[ei] (that is, now 3 < 6), si will again move right by one location to arr[2]
- Because arr[si] < arr[ei] (that is, now 0 < 6), si will again move right by one location to arr[3]
- Because arr[si] < arr[ei] (that is, now 2 < 6), si will again move right by one location to arr[4]
- Because arr[si] > arr[ei] (that is, now 7 > 6), interchanging of their values will take place (see Figure 9.24):
After interchanging of values at arr[ei] and arr[si], the location number of arr[si], that is, 4, will be assigned to li. The process is repeated; that is, again a while loop is set to execute while arr[ei] > arr[si]. Within the while loop, the location of ei is decremented, or it moves to the left:
While comparing arr[ei] and arr[si], we will find that arr[ei] > arr[si] (7 > 6), so ei will be decremented to value 6 (see Figure 9.26(a)). Again, because arr[ei] < arr[si] (1 < 6), interchanging of values of these index locations will take place (see Figure 9.26(b)). The location number of ei, 6 now, will be assigned to variable li.
Another while loop is set to execute while arr[si] < arr[ei] (remember the location number of ei is assigned to li). The following things will happen in this while loop:
- Because arr[si] < arr[ei] (that is, 1 < 6), si will move right to arr[5]
- Because still arr[si] < arr[ei] (that is, 5 < 6), si will move right to arr[6]
- Because now the location of ei and si are the same, the quick function will terminate returning the number 6 to the main function (see Figure 9.26(c)). So, the number 6 will become the pivot of the arr array.
Two if statements are executed and the array is split into two parts: the first part ranges from arr[0] to arr[5] and the other part from arr[7] to arr[7], that is, of a single element. The first and last index values of the two parts of the array are pushed to the stack.
The first and last index locations of the second part of the array, that is, 7, will be pushed to both stack1 and stack2. The first and last index locations of the first part of array, that is, 0 and 5, will also be pushed to stack1 and stack2, respectively (see Figure 9.27).
The complete quick sort technique is applied on both halves of the array. Again, the two halves will be partitioned into two more parts and again the quick sort technique is applied on those two parts, and so on.
The outer while loop repeats and the popstk1() and popstk2() functions will be invoked to pop off the values in the stack1 and stack2 arrays. The values of the top1 and top2 indices are 1, so the values at the stack1[1] and stack2[1] index locations are picked up and assigned to the two variables, sindex and eindex, respectively. Again, the quick() function is invoked and the two variables, sindex and eindex, are passed to it. In the quick function, the values of the sindex and eindex arguments are assigned to the si and ei parameters respectively
Within the quick() function, the value of the si variable, that is, 0, is assigned to another variable, li. A while loop is executed in an infinite loop. Within the while loop, another while loop is set to execute that will make the ei index location to move toward the left, that is, it will make the value of the ei index variable decrement for the time the element at the arr[ei] location is greater than the arr[si] location (see Figure 9.28(a)). Because arr[ei] > arr[si], the value of the ei variable will be decremented to 4 (see Figure 9.28(b)). Now, we find that arr[ei], that is, 1 is less than arr[si], that is, 4, so interchanging of their values will take place. After interchanging the values at that arr[ei] and arr[si] index locations, the arr array will appear as shown in Figure 9.28(c).
After interchanging the values, the value of the ei variable is assigned to the li variable, that is, 4, is assigned to the li variable. Another while loop is set to execute while the arr[si] element is smaller than arr[li], where li represents the si index currently; and within the while loop, the value of the si index pointer is incremented. The following things will happen:
- Because arr[si], that is, 1, is less than arr[ei], that is, 4, si will be incremented to a value of 1.
- Because arr[si], that is, 3, is less than arr[ei], that is, 4, si will be incremented to a value of 2.
- Because arr[si], that is, 0, is less than arr[ei], that is, 4, si will be incremented to a value of 3.
- Because arr[si], that is, 2, is less than arr[ei], that is, 6, si will be incremented to a value of 4.
Because the values of the ei and si variables have become the same, the quick() function will terminate, returning the value 4 to the main function (see Figure 9.28(d )):
On returning to the main function, two if statements are executed and the array is split into two parts: the first part ranges from the arr[0] to the arr[3] index locations, and the other part will range from the arr[5] to the arr[5] index locations, that is, of a single element. The starting and ending index values of the two parts of the array are pushed to the stack. The starting and ending index locations of the second part of the array (that is, 5 and 5) will be pushed to stack1 and stack2, respectively. Similarly, the starting and ending index locations of the first part of the array (that is, 0 and 3) are pushed to stack1 and stack2, respectively (see Figure 9.29).
The whole quick sort technique is applied on all the partitions of the array until the stacks are empty. That is, the outer while loop repeats and the popstk1() and popstk2() functions will be invoked to pop off the values in the stack1 and stack2 arrays. Again, the quick() function is invoked and the two variables, sindex and eindex, that are popped from the stack are passed to it. The procedure continues until the whole array is sorted.
The program is compiled using GCC using the following statement:
gcc quick sort.c -o quick sort
Because no error appears on compilation, that means the quick sort.c program has successfully been compiled into the quick sort.exe file. On executing the file, it will ask you to specify how many numbers there are to be sorted. Following this, the program will prompt you to enter the numbers to be sorted. After entering the numbers, they will appear sorted in ascending order, as shown in the following screenshot:
Voilà! We have successfully arranged the numbers in our array using quick sort. Now let's move on to the next recipe!