python program for quick sort algorithm
By Prakash RajIn this program, we are going to learn the quicksort algorithm using Divide and conquer approaches/method in Python.
What is the divide and conquer approaches
Divide and conquer approaches is the most useful and easy method to implement the algorithm, in this method generally we divide the whole set of element till the singleton element and then conquer them.
now move on the coding part :
1st implement the function with the name of the partition to find out the exact position of a pivot element in the array.
#use to find out pivot element
def partition(array,f,l):
#index of smaller element
i=f-1
# pivot element
pivot= array[l]
for j in range(f,l):
# If current element is smaller than or
# equal to pivot
if array[j]<= pivot:
# increment index of smaller element
i = i+1
array[i],array[j] = array[j],array[i]
array[i+1],array[l] = array[l],array[i+1]
return i+1
now implement the main function for recursive call:
# The main function that implements QuickSort
# arr[] --> Array to be sorted,
# f--> Starting index,
# l --> Ending index
# Function to do Quick sort
def QuickSort(arr,f,l):
if f < l:
# pi is partitioning index, array[p] is now
# at right place
p = partition(array,f,l)
# Separately sort elements before
# partition and after partition
QuickSort(array,f, p-1)
QuickSort(array, p+1,l)
at last, take an array and call the function QuickSort and print the output result:
# Driver code to test above
array = [10,63,6,5,9,7]
n = len(array)
QuickSort(array,0,n-1)
print ("Sorted array is:")
for i in range(n):
print ("%d" %array[i]),
Quicksort using divide and conquer method in Python
Now combine the whole code:
def partition(array,f,l):
#index of smaller element
i=f-1
# pivot element
pivot= array[l]
for j in range(f,l):
if array[j]<= pivot:
# increment index of smaller element
i = i+1
array[i],array[j] = array[j],array[i]
array[i+1],array[l] = array[l],array[i+1]
return i+1
def QuickSort(arr,f,l):
if f < l:
p = partition(array,f,l)
QuickSort(array,f, p-1)
QuickSort(array, p+1,l)
# Driver code to test above
array = [10,63,6,5,9,7]
n = len(array)
QuickSort(array,0,n-1)
print ("Sorted array is:")
for i in range(n):
print ("%d" %array[i]),
Output:
Sorted array is: 5 6 7 9 10 63
You may also read:
Leave a Reply