Question

Write a program to implement Quick Sort

Answer 1

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