# Write a program to implement Quick Sort

0 like 0 dislike
355 views

recategorized

Write a program to implement Quick Sort

0 like 0 dislike
by Goeduhub's Expert (7.6k points)
edited

## Ques.Write a program to implement Quick Sort

Answer : Quicksort is a  sorting algorithm that uses divide-and-conquer algorithm. It works by selecting a "key" element  or can say "pivot" element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Example :

A = [20, 90, 40, 100, 50, 60, 80]

low = 0, high =  6, pivot = A[h] = 80

let index of smaller element, i = -1

Traverse from j = low to high-1

j = 0 : A[j] <= pivot,  increase i and swap(A[i], A[j])

i = 0

A[] = {20, 90, 40, 100, 50, 60, 80} // No change as i and j are same

j = 1 : A[j] > pivot,do nothing//No change in i and A[]

j = 2 :  A[j] <= pivot, do i++ and swap(A[i], A[j])

i = 1

A[] = {20, 40, 90, 100, 50, 60, 80} // We swap 80 and 30

j = 3 : A[j] > pivot, do nothing // No change in i and A[]

j = 4 : Since A[j] <= pivot, do i++ and swap(A[i],A[j])

i = 2

A[] = {20, 40, 50, 100, 90, 60, 80} // 90 and 50 Swapped

j = 5 : Since A[j] <= pivot, do i++ and swap A[i] with A[j]

i = 3

A[] = {20, 40, 50, 60, 90, 100, 80} // 100 and 60 Swapped

Now , because j == equal to high-1 we need to move out of loop.

Finally we place pivot at correct position by swapping

A[i+1] and A[high] (or pivot)

A[] = {20, 40, 50, 60, 80, 100, 90} // 90 and 80 Swapped

Now 80 is at its correct place. All elements smaller than

80 are before it and all elements greater than 80 are after

it.

Algorithm :

quickSort(arr[], low, high)
{
if (low < high)
{
pi = partition(arr, low, high)

quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
}
}

Program :

def div(arr,low,high):

i = ( low-1 )

key= arr[high]

for j in range(low , high):

if   arr[j] <= key:

i = i+1

arr[i],arr[j] = arr[j],arr[i]

arr[i+1],arr[high] = arr[high],arr[i+1]

return ( i+1 )

def quickSort(arr,low,high):

if low < high:

pi = div(arr,low,high)

quickSort(arr, low, pi-1)

quickSort(arr, pi+1, high)

a= input("enter elements you want to sort : ")

arr=a.split(",")

n = len(arr)

quickSort(arr,0,n-1)

print ("Sorted array is:",end="")

for i in range(n):

print ( arr[i],",",end="")

Output :

enter elements you want to sort : 4,5,6,3,2,1

Sorted array is:1 ,2 ,3 ,4 ,5 ,6 ,

## For more Rajasthan Technical University CSE-III Sem DSA Lab Experiments  CLICK HERE

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.