Introduction

The quick sort algorithm is based on Divide and Conquer. The task is to sort the given array element using quick sort.

Program

def divide(ip_arr, low, high):
    i = (low - 1)
    pvt_ele = ip_arr[high]
    for j in range(low, high):
        if ip_arr[j] <= pvt_ele:
            i = i + 1
            ip_arr[i], ip_arr[j] = ip_arr[j], ip_arr[i]
    ip_arr[i + 1], ip_arr[high] = ip_arr[high], ip_arr[i + 1]
    return(i + 1)
def sort(ip_arr, low, high):
    if len(ip_arr) == 1:
        return arr
    if low < high:
        idx = divide(ip_arr, low, high)
        sort(ip_arr, low, idx-1)
        sort(ip_arr, idx + 1, high)


ip_arr = [90, 89, 15, 7]
print("The input array is: ", ip_arr)
print("The sorted array is :")
for i in range(len(ip_arr)):
    print("%d"%ip_arr[i])

Output

Explanation

The elements are partitioned around the pivot element. There are multiple ways to select the pivot element i8n the array.

• Select the first element
• Select the last element
• Select median
• Select random element from the array

The pivot element is placed at the correct position and all the smaller and greater elements are placed left and right to it respectively. The resultant array is displayed using print function.