**Description**: This method is invented by hoare, considered to be fast method to sort the elements. The method is also called partition exchange sorting. The method is based on divide and conquer technique. i.e., the entire list is divided into various partitions and sorting is applied again and again on the partition.

In this method the list is divided into two baesd on an element called pivot element. Usually the first element is considerd to be the pivot element. Now move the pivot element to its correct position in the list. The elements to the left and pivot element are less that this while the elements to the right of pivot are greater than the pivot. The process is reapplied to each of these partitions till we got the sorted list of elements.

**Algorithm:**

**Quick Sort:**

1. start

2. if lowerbound < upperbound repeat through steps 3 to 13 otherwise

goto step 14

begin

3. assign lowerbound to i,upperbound to j, i to pivot

4. if i<j repeat through steps 5 to 10 otherwise goto step _

Begin

5. if a[i]<=k[pivot] and i< upperbound repeat through step 6 otherwise

goto step 7

begin

6. assign i+1 to i

end if

7. if k[j] > k[pivot] repeat through step 8 otherwise goto step 9

begin

8. assign j-1 to j

end if

9. if i< j goto step 10 other wise goto step 4

Begin

10. call function to swap k[i] and k[j]

end if

end if

11. call function to swap k[pivot] and k[j]

12. call function qsort(x,lowerbound,j-1)

13. call function qsort(x,j+1,upperbound)

end if

14. stop

**Program:**

#include<stdio.h>

main()

{

int x[10],i,n;

clrscr();

printf("enter no of elements:");

scanf("%d",&n);

printf("enter %d elements:",n);

for(i=1;i<=n;i++)

scanf("%d",&x[i]);

quicksort(x,1,n);

printf("sorted elements are:");

for(i=1;i<=n;i++)

printf("%3d",x[i]);

getch();

}

quicksort(int x[10],int first,int last)

{

int pivot,i,j,t;

if(first<last)

{

pivot=first;

i=first;

j=last;

while(i<j)

{

while(x[i]<=x[pivot] && i<last)

i++;

while(x[j]>x[pivot])

j--;

if(i<j)

{

t=x[i];

x[i]=x[j];

x[j]=t;

}

}

t=x[pivot];

x[pivot]=x[j];

x[j]=t;

quicksort(x,first,j-1);

quicksort(x,j+1,last);

}

}

enter no of elements:6

enter 6 elements:23

12

45

34

21

87

sorted elements are: 12 21 23 34 45 87

**conclusion:**The program is error free

__VIVA QUESATIONS__**1)**Define quick sort ?

**Ans:**

This method is invented by hoare, considered to be fast method to sort the elements. The method is also called partition exchange sorting. The method is based on divide and conquer technique. i.e., the entire list is divided into various partitions and sorting is applied again and again on the partition.

In this method the list is divided into two baesd on an element called pivot element. Usually the first element is considerd to be the pivot element. Now move the pivot element to its correct position in the list. The elements to the left and pivot element are less that this while the elements to the right of pivot are greater than the pivot. The process is reapplied to each of these partitions till we got the sorted list of elements.

**2)**Efficiency of quick sort ?

**Ans:**O(n log n)

## No comments:

## Post a Comment