Question

Write a program in python that implements quicksort, first using recursion and then without recursion.

Answer 1

Using Recursion:

def make_partition(arr, low, high):
        i = (low-1)              # index of smaller element
        temp = arr[high]

        for j in range(low, high):
                # If current element is smaller than or equal to temp then swap
    #element and increment i by 1
                if arr[j] <= temp:
                        i = i+1
                        arr[i], arr[j] = arr[j], arr[i] #swap element

        arr[i+1], arr[high] = arr[high], arr[i+1]
        return (i+1)

def quickSort(arr, low, high):
  #check if array has only one element the return array
        if len(arr) == 1:
                return arr
        if low < high:
                #fnd partitioning_index by calling function make_partition()
                partitioning_index = make_partition(arr, low, high)

                #sort elements before partition and after partition
                quickSort(arr, low, partitioning_index-1)
                quickSort(arr, partitioning_index+1, high)

#empty array to be sorted
arr = []

#get number of element from user
size = int(input("Enter how many element you want to sort : "))

#get one by one element from user 
for i in range(1,size+1):
  element = int(input("Enter element of "+str(i)+" : "))
  arr.append(element)

#call function to sort array
quickSort(arr, 0, size-1)

#print sorted array
print(("-"*20)+" Sorted Array "+("-"*20))

for i in range(size):
        print("%d" % arr[i])

Output:

Without Recursion:

def partition(arr,l,h): 
    i = ( l - 1 ) 
    x = arr[h] 
  
    for j in range(l , h):
        # If current element is smaller than or equal to temp then swap
        #element and increment i by 1 
        if   arr[j] <= x: 
            i = i+1
            arr[i],arr[j] = arr[j],arr[i] 
  
    arr[i+1],arr[h] = arr[h],arr[i+1] 
    return (i+1) 

def quickSort(arr,l,h): 
  
    # Create stack 
    size = h - l + 1
    stack = [0] * (size) 
  
    # initialize top of stack 
    top = -1
  
    # push values of l and h to stack 
    top = top + 1
    stack[top] = l 
    top = top + 1
    stack[top] = h 
  
    # Keep popping from stack while is not empty 
    while top >= 0: 
  
        # Pop h and l 
        h = stack[top] 
        top = top - 1
        l = stack[top] 
        top = top - 1
  
        # Set middle element at its correct position in 
        # sorted array 
        middle = partition( arr, l, h ) 
  
        # If there are elements on left side of middle, 
        # then push left side to stack 
        if middle-1 > l: 
            top = top + 1
            stack[top] = l 
            top = top + 1
            stack[top] = middle - 1
  
        # If there are elements on right side of middle, 
        # then push right side to stack 
        if middle+1 < h: 
            top = top + 1
            stack[top] = middle + 1
            top = top + 1
            stack[top] = h 
  


#empty array to be sorted
arr = []

#get number of element from user
size = int(input("Enter how many element you want to sort : "))

#get one by one element from user 
for i in range(1,size+1):
  element = int(input("Enter element of "+str(i)+" : "))
  arr.append(element)

#call function to sort array
quickSort(arr, 0, size-1)

#print sorted array
print(("-"*20)+" Sorted Array "+("-"*20))

for i in range(size):
        print("%d" % arr[i])

Output: