python program for quick sort algorithm

In 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

Your email address will not be published.