## QUICK SORT IN C

Back to Quick Sort

Quick Sort is another sorting algorithm that is based on divide and conquer approach. Unlike merge sort that divides input elements according to their position in array, quick sort divides input element according to their values. Here is a three-step divide and conquer process for sorting a typical sub-array.

Need Python Homework Help: Get Python Homework Help from Epert

Divide : Partition or rearrange the array a[p . . r] into two sub-arrays a[ p . . q-1 ] and a[q+1 . . r] such that a[ p . . q-1 ] <= a[q] <= a[q+1 . . r] . Compute the index q as part of this partition procedure. Here a[q] is called the pivot element.

Conquer : Sort the two sub-arrays a[ p . . q-1 ] and a[q+1 . . r]  by recursive calls to quick sort.

Combine : Because the sub-arrays are already sorted, no work is needed to combine them : the entire array a[ p . . r ] is now sorted.

Lets understand Quick Sort with the help of an example :

Array Elements ( List ) : 2 8 7 1 3 5 6 4

Steps :

• Select the pivot element ( 4 in this case )
• Rearrange elements such that elements before pivot element are less than it and element after pivot element are greater than it. This arrangement of elements in accordance with the pivot element is called partition operation.
• Sort the sub-array recursively. Steps for Quick Sort
• The above image shows the partition of Array elements ( Initial list ).
• Similarly the two sub-array before and after pivot element are partitioned.
• The complete steps of quick sort is shown below.

## QUICK SORT ALGORITHM

`// Algorithm for Quick Sort`
```
```
```QUICKSORT(a, p, r)
if p<r
q = PARTITION(a, p, r)
QUICKSORT(a, p, q-1)```
`    QUICKSORT(a, q+1, r)`

Partitioning the array :

```PARTITION(a, p, r)
x=a[r]
i=p-1
```
```  for j=p to r-1
if(a[j]<=x)
i=i+1
swap a[i] with a[j]```
`  end loop`
```
swap a[i+1] with a[r]```
`  return i+1`

## QUICK SORT PROGRAM IN C

```//Quick sort program ( code ) in c

#include<stdio.h>

void quicksort(int a[],int p, int r);
int partition(int a[],int p, int r);

int main()
{
int a,i,n;
printf("Enter number of elements in array : ");
scanf("%d",&n);

// Inputting elements
for(i=0;i<n;i++)
{
printf("Enter number %d: ",i+1);
scanf("%d",&a[i]);
}

// Displaying Elements before quick sort
printf("Items in the array are : ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}

//Applying quick sort
quicksort(a,0,n-1);

// Displaying elements after quick sort
printf("\nElements after quick sort : ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
return 0;
}

void quicksort(int a[],int p, int r)
{
int q;
if(p<r)
{```
```     // q - index at which pivot element lies
q=partition(a,p,r);```
```
```
```     // Sorting sub-array recursively
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}

int partition(int a[],int p, int r)
{
int temp;```
`   int i=p-1;`
`   int j;`
```
```
```   // pivot element around which partition is done
int x=a[r];```
```
for(j=p;j<=r-1;j++)
{
if(a[j]<=x)
{
i=i+1;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}

temp=a[i+1];
a[i+1]=a[r];
a[r]=temp;
return (i+1);
}
```

## Quick Sort Program Output Quick Sort : Quick Sort Program Output

## Searching And Sorting In C

Other Searching and Sorting technique will be published soon.

## Merge Sort Program In C

Here I am providing you with Merge Sort program in c.
```#include<stdio.h>

void mergesort(int a[],int i, int j);
void merge(int a[],int p , int q, int r1);

int main()
{
int a,i,n,item;
printf("Enter number of elements in array : ");
scanf("%d",&n);

// Inputting elements
for(i=0;i<n;i++)
{
printf("Enter number %d: ",i+1);
scanf("%d",&a[i]);
}

// Displaying Elements before merge sort
printf("Items in the array are : ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}

//Applying merge sort
mergesort(a,0,n-1);

// Displaying elements after merge sort
printf("\nElements after merge sort : ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
return 0;
}

void mergesort(int a[],int i, int j)
{
int mid;
if(i>=j)
return;

else
{
mid=(i+j)/2;
mergesort(a,i,mid);
mergesort(a,mid+1,j);
merge(a,i,mid,j);
}
}

void merge(int a[],int p , int q, int r)
{
int n1=q-p+1;
int n2=r-q;
int left[n1+1];
int right[n2+1];

int i=0;
int j=0;
int k=0;

for(i=0;i<n1;i++)
{
left[i]=a[p+i];
}

for(i=0;i<n2;i++)
{
right[i]=a[q+i+1];
}

left[n1]=9999;
right[n2]=9999;

i=0;
j=0;

for(k=p;k<=r;k++)
{

if(left[i]<right[j])
{
a[k]=left[i];
i++;
}

else
{
a[k]=right[j];
j++;
}
} ```
```}

```