**Write C programs for implementing the Quick sorting****Algorithm****to arrange a list of integers in ascending order.**

**Quick Sort algorithm:***• It was developed by C.A.R Hoare in 1962.*

*• Like bubble sort, quick sort is an exchange sort, i.e., items swap positions till the entire array is sorted.*

*• The quickSort is more efficient because it requires fewer exchanges to correctly position an element.*

**The basic principle of Quick sort algorithm:***• Pick one element in the array and rearrange the remaining elements around it. The chosen element is called the pivot(usually first element of the list).*

*• Once the pivot is chosen, all the elements lesser than the pivot are moved to the left of the pivot, and all elements equal to or greater than the pivot are moved to the right of the pivot.*

*• The pivot acts as a partition dividing the original list into two sub lists, and after the partitioning, the pivot is in its correct position in the sorted list.*

*• This procedure of choosing the pivot and partitioning the list is recursively applied to the sub lists till the subsequent sub lists consists of only one element.*

**The complexity of quick sort algorithm:***Best case: O(n log n)*

*Average case:O(n log n)*

*Worst case: O(n2)*

**Quick Sort Algorithm:***void qsort(int a[10],int first,int last)*

*step 1 : start*

*step 2 : declare integer variables*

*i,j,t,pivot,n;*

*step 3: check up to first less than last*

*if(first<last) [step 3 to step 10]*

*i=first;*

*j=last;*

*pivot=first;*

*step 4: repeat upto first less than last from step 4 to step 10*

*while(i<j)*

*step 5: repeat 5 to 7*

*while(a[i]<=a[pivot]&&i<last)*

*i++;*

*step 6 : while(a[j]>a[pivot])*

*j--;*

*step 7: if(i<j)*

*{*

*t=a[i];*

*a[i]=a[j];*

*a[j]=t;*

*}*

*step 8: t=a[pivot];*

*a[pivot]=a[j];*

*a[j]=t;*

*step 9: qsort(a,first,j-1);*

*step 10: qsort(a,j+1,last);*

*step 11: stop*

**Algorithm: Main function***step 1: start*

*step 2: declare i,n,a[10]*

*step 3: Read the size of an array*

*step 4: Read the elements of an array*

*step 5: call sub function qsort(a,0,n-1);*

*step 6: print sorted elements of an array a[i]*

*step 7: stop*

**Thanks**

**Mukesh Rajput**
## Post A Comment:

## 0 comments:

Thanks

Mukesh Rajput