Sorting in data Structures:
4. Quick Sorting
5. Merge Sorting
Note: In this page you will see the next part of sorting.
4. Quick Sorting:
1. Quick Sort is a process of Dividing and Conquering the algorithm. It will pick an element as pivot and it will partitions the given array of elements around the picked pivot.
2. There are different versions of quick Sorting that picks pivot in many ways.
1. Always first pick element as pivot.
2. Always pick the last element as pivot (implemented below)
3. Now pick a random element as pivot.
4. And at last pick median as pivot. The key process in quick Sort will be partition().
All this process should be finished in a linear time.
Program for Quick sorting:
#include<stdio.h>
#include<conio.h>
void quicksort(int[],int,int);
void main()
{
int x[20],i,n;
clrscr();
printf("Enter size of list:");
scanf("%d",&n);
printf("Enter %d elements:",n);
for(i=0;i<n;i++)
scanf("%d",&x[i]);
quicksort(x,0,n);
printf("Sorted List:");
for(i=0;i<n;i++)
printf("%d\t",x[i]);
getch();
}
void quicksort(int x[20],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);
}
}
5. Merge sorting:
It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves.
Program for Merge Sorting:
#include <stdio.h>
#include <stdlib.h>
void merge(int a[],int,int,int);
void mergesort(int a[],int,int);
void main()
{
int a[20],i,n;
clrscr();
printf("Enter size of List:");
scanf("%d",&n);
printf("\nEnter %d elements: \n",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
mergesort(a,0,n-1);
printf("Sorted List:");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
getch();
}
void mergesort(int a[],int beg,int end)
{
int mid;
if(beg<end)
{
mid=(beg+end)/2;
mergesort(a, beg, mid);
mergesort(a, mid + 1, end);
merge(a,beg,mid,end);
}
}
void merge(int a[],int beg,int mid,int end)
{
int i=beg,j = mid+1,index=beg,temp[20],k;
while((i<=mid)&&(j<=end))
{
if(a[i]<a[j])
{
temp[index]=a[i];
i++;
}
else
{
temp[index]=a[j];
j++;
}
index++;
}
if(i>mid)
{
while(j<=end)
{
temp[index]=a[j];
j++;
index++;
}
}
else
{
while(i<=mid)
{
temp[index]=a[i];
i++;
index++;
}
}
for(k=beg;k<index;k++)
a[k]=temp[k];
}
Note: For remaining sorting refer to the part 1 page on sorting.
0 Comments