Program for quick sort in Python

Introduction

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

Program for quick sort in Python

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

Program for quick sort in Python 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.

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.