c program and algorithm of quick sort

Rajnish

 what is quick sort:-

                                 Quick sort is one of the most efficient sorting technique because it is work on divide and conquer method.

–> the Quick sort algorithm work by partitioning the array to be sorted.

Algorithm:-

                    Here A  is the array with N elements . Parameters BEG and END contain the boundary values of the sublist of A to which this procedure applies . LOC keeps track of the position of the first element A[BEG] of the sublist during the procedure . The local variables 

LEFT and RIGHT will contain the boundary value of the list of elements that have not been scanned.


1. Set LEFT=BEG ,RIGHT=END  and LOC=BEG

2. Scan from Right to Left

      (a). Repeat while  A[LOC]<=A[RIGHT] and LOC!=RIGHT

                    RIGHT=RIGHT-1

      (b). If  LOC==RIGHT then Return .

       (c). If  A[LOC]>A[RIGHT] then 

                (i). Interchange A[LOC] and A[RIGHT]       

                             TEMP=A[LOC]

                              A[LOC]=A[RIGHT]

                              A[RIGHT]=TEMP 

                (ii). Set LOC=RIGHT

                (iii). Go to step 3     

3. Scan from left to right 

    (a). Repeat while A[LEFT]<=A[LOC] and LOC!=LEFT

                   LEFT=LEFT-1

     (b). If LEFT==LOC then Return.

     (c). If A[LEFT]>A[LOC] then 

               (i). Interchange A[LOC] and A[LEFT]

                            TEMP=A[LEFT]

                             A[LEFT]=A[LOC]

                             A[LOC]=TEMP 

                 (ii). Set LOC=LEFT

                  (iii). GO to step 2 

Code:-

#include<stdio.h>
int a[100];

// function for swap the values
void swap(int x,int y)
{
int temp;
temp=a[x];
a[x]=a[y];
a[y]=temp;
}

// function for make the partition
int partition(int left,int right)
{
int loc=left;
while(left<right)
{
while(a[right]>=a[loc] && loc!=right )
right–;
if(a[loc]>a[right])
swap(loc,right);
while(a[left]<=a[loc] && loc!=left)
left++;
if(a[left]>a[loc])
swap(left,loc);
}
return loc;
}

// function for quick sort
void quick_sort(int left,int right)
{
int loc;
if(left<right)
{
loc=partition(left,right);
// calling of the quick_sort for the left side elements
quick_sort(left,loc–1);
// calling of the quick_sort for the right side elements
quick_sort( loc+1,right);
}
}
int main()
{
int n;
printf(“Enter size of the arrayn”);
scanf(“%d”,&n);
printf(“Enter element of the arrayn”);
for(int i=0;i<n;i++)
scanf(“%d”,&a[i]);
printf(“Array before sorting :-n”);
for(int i=0;i<n;i++)
printf(“%d “,a[i]);
printf(“n”);
// function calling
quick_sort(0,n–1);
printf(“Sorted array is:-n”);
for(int i=0;i<n;i++)
printf(“%d “,a[i]);
return 0;
}

Output:-

Enter the size of the array
5
Enter the element of the array
12 43 2 32 1
Array before sorting:-
12 43 2 32 1
Sorted array is:-
1 2 12 32 43




Leave a Reply

Your email address will not be published.