Table of Contents
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.
0 Comments