Thursday, 28 December 2017

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

No comments:

Post a Comment

Thanks
Mukesh Rajput