Python program for Iterative QuickSort

Iteration is the process of repeating the execution of a collection of statements. In this tutorial, we will perform an iterative QuickSort sort operation to sort an array.

Iterative QuickSort - A basic Introduction

In this approach, we first partition the array and sort the separate partition to get the sorted array. Let us have a rough understanding of how this method is performed:

1. Take the rightmost element as the pivot
2. All components smaller than pivot should be pushed to the left, while bigger elements should be pushed to the right.
3. Replace the rightmost element with the Index element.
4. Return the index
5. Perform QuickSort with help of the above partition method
6. Now, the array is sorted

Algorithm for Iterative QuickSort

We have already seen the recursive QuickSort operation and we have basic knowledge on how QuickSort operation is done but iterative QuickSort is very different let's have a look at the Algorithm followed by the code:

1. Create a function partition()
2. Pass three-parameter array, low, high
3. increment index of the smaller element
4. Create a function I_QuickSort()
5. Pass three-parameters array, low, high
6. Create Stack and initialize the top of the stack
7. Push the initial value of low and high and keep popping it
8. Set pivot element to its correct position
9. Print the sorted array

In the iterative QuickSort operation, all variables are declared inside a local scope as given in the below diagram:

Program for Iterative QuickSort

In this program, we use a stack to store the subarray's starting and ending position for processing the stack later. Now it's time for the code with influence from the Algorithm:

def partition(array,low,high):
    i = ( low - 1 )
    x = array[high]
 
    for j in range(low , high):
        if   array[j] <= x:
 
            i = i+1
            array[i],array[j] = array[j],array[i]
 
    array[i+1],array[high] = array[high],array[i+1]
    return (i+1)
 
# low  --> Starting index,
# high  --> Ending index
def I_QuickSort(array,low,high):
 
    #  auxiliary stack
    size = high - low + 1
    stack = [0] * (size)
 
    top = -1
 
    top = top + 1
    stack[top] = low
    top = top + 1
    stack[top] = high
 
    # Keep popping from stack while is not empty
    while top >= 0:
 
        # Pop high and low
        high = stack[top]
        top = top - 1
        low = stack[top]
        top = top - 1
 
        # sorted array
        p = partition( array, low, high )

        # push left side to stack
        if p-1 > low:
            top = top + 1
            stack[top] = low
            top = top + 1
            stack[top] = p - 1

        #  push right side to stack
        if p+1 < high:
            top = top + 1
            stack[top] = p + 1
            top = top + 1
            stack[top] = high
 
# Driver code 
array = [9, 0, 8, 1, 7, 3, 6, 4]
n = len(array)
print("Orignal Array:", array)
I_QuickSort(array, 0, n-1)
print ("Sorted Array :", array)

Orignal Array: [9, 0, 8, 1, 7, 3, 6, 4]
Sorted Array : [0, 1, 3, 4, 6, 7, 8, 9]

Conclusion

In this tutorial, we have performed an Iterative QuickSort Operation in python programming to sort a given array.