Implementation of Quick Sort

AIM:

          To write a C program to implement Quick sort

ALGORITHM:

            Step 1: Start the program.

Step 2: Declare the function quicksort(array)

Step 3: less, equal, greater := three empty arrays

Step 4: if length(array) > 1 

Step 5: Then pivot := select any element of array

Step 6: for each x in array

            if x < pivot then add x to less

            if x = pivot then add x to equal

            if x > pivot then add x to greater

        quicksort(less)

        quicksort(greater)

Step 7: array := concatenate(less, equal, greater)

Step 8: Stop the program.

PROGRAM

#include<stdio.h>

void quicksort(int [10],int,int);

int main()

{

int x[20],size,i;

printf("Enter size of the array: ");

scanf("%d",&size);

printf("Enter %d elements: ",size);

for(i=0;i<size;i++)

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

quicksort(x,0,size-1);

printf("Sorted elements: ");

for(i=0;i<size;i++)

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

return 0;

}

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

{

int pivot,j,temp,i;

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)

{

temp=x[i];

x[i]=x[j];

x[j]=temp;

}

}

temp=x[pivot];

x[pivot]=x[j];

x[j]=temp;

quicksort(x,first,j-1);

quicksort(x,j+1,last);

}

}

OUTPUT

Enter size of the array: 5

Enter 5 elements: 3 8 0 1 2

Sorted elements: 0 1 2 3 8

  

RESULT: Thus a C program is written to implement quick sort and executed

                    successfully