[go: up one dir, main page]
Scribd
Upload
8 views17 pages

Merging or Merge Sort

The document explains two sorting algorithms: Merge Sort and Quick Sort. Merge Sort divides the input array into halves, recursively sorts them, and merges the sorted halves, while Quick Sort selects a pivot and partitions the array into elements less than and greater than the pivot, recursively sorting the partitions. Both algorithms are illustrated with examples and include corresponding C programming implementations.

Uploaded by

akkutuppu
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
8 views17 pages

Merging or Merge Sort

The document explains two sorting algorithms: Merge Sort and Quick Sort. Merge Sort divides the input array into halves, recursively sorts them, and merges the sorted halves, while Quick Sort selects a pivot and partitions the array into elements less than and greater than the pivot, recursively sorting the partitions. Both algorithms are illustrated with examples and include corresponding C programming implementations.

Uploaded by

akkutuppu
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 17

Merge Sort & Quick Sort

Merging or Merge Sort:


 It divides input array into two halves, calls itself for the two halves and then
sorted and merged that two halves.
Example:
 For example consider the array of elements: 38, 27, 43, 3, 9, 82, 10
 Now the array is recursively divided into two halves till the size becomes one
which is shown in the following figure.
 Once the size becomes one, the merge process comes into action and starts
merging with sorted array till the complete array is merged
Algorithm:
Step 1 − If it is only one element in the list then it is already sorted.
Step 2 − Divide the list recursively into two halves till the size becomes one.
Step 3 − Once the size becomes 1, the merge process comes into action and starts
merging with sorted array till the complete array is merged
Program:
#include<stdio.h>
int n,a[30],i,j,k,temp[30];
void merge(int low,int mid,int high)
{
i=low;
j=mid+1;
k=low;
while((i<=mid) && (j<=high))
{
if(a[i]>=a[j])
temp[k++]=a[j++];
else
temp[k++]=a[i++];
}
while(i<=mid)
temp[k++]=a[i++];
while(j<=high)
temp[k++]=a[j++];
for(i=low;i<=high;i++)
a[i]=temp[i];
}
void mergesort(int low,int high)
{
int mid;
if(low!=high)
{
mid=((low+high)/2);
mergesort(low,mid);
mergesort(mid+1,high);
merge(low,mid,high);
}
}
int main()
{
printf("Enter total elements:\n");
scanf("%d",&n);
printf("Enter elements:\n");
Output:
for(i=0;i<n;i++) Enter total elements:
5
scanf("%d",&a[i]);
Enter elements:
mergesort(0,n-1); 50 10 40 20 30
printf("After sorting is:\n"); After sorting is:
10 20 30 40 50
for(i=0;i<n;i++)
printf(" %d",a[i]);
return 0;
}
Quick Sort:
 Quick Sort is also one of the exchange sort.
 In a quick sort we take pivot element, then we place all the smaller elements are
on one side of pivot, and greater elements are on other side of pivot.
 After partitioning we have pivot in the final position. After repeatedly
partitioning, we get the sorted elements.

Example:
 Let us consider the elements:
35,50,15,25,80,20,90,45
 Let us consider the first element 35 as pivot or i. The last element 45 as j
 50 which is greater than pivot taken as i and the 20 smaller than pivot taken as j

 Now i is less than j so swap the elements in i and j.

 Find greater than 35 (80)is i and less than 35(25) is j


 Now i is not less than j. swap 35 and j so 35 becomes at j place.

 Now 35 is in correct position.


 On left side and right side of 35 repeat the process. Consider on left side of 35

 Let 25 as pivot. The lesser of 25 that is 15 as j and there is no greater. So bring i after j i > j
so swap pivot and j
 After swapping

 Now the left part is sorted. Consider right part

 Here 80 as pivot, Greater than to 80 is i and less than to 80 is j


 Here i is less than j so swap i and j elements.

 first find greater to 80 is i and lesser to 80 is j. i > j so swap 80 and j.

 After swapping. The sorting elements are given by


 Now join all left part j and right part j to get the sorted elements

Algorithm:

Step 1: Let the first element taken as pivot


Step 2: Find lesser of pivot say i and greater of pivot say j.
Step 3: If i is less than j then i and j elements are swapped. Repeat step 2
Step 4: Repeat step 3 until i > j
Now swap j and pivot
Step 5: Now the pivot element is final position.
Repeat the above procedure for left and right side of pivot elements until all
elements are sorted
Step 6: Stop
Program:
#include<stdio.h>
void quicksort(int a[25],int first,int last)
{
int i, j, pivot, temp;
if(first<last)
{
pivot=first;
i=first;
j=last;
while(i<j)
{
while(a[i]<a[pivot]&&i<=last)
i++;
while(a[j]>a[pivot])
j--;
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[pivot];
a[pivot]=a[j];
a[j]=temp;
quicksort(a,first,j-1);
quicksort(a,j+1,last);
}
}
int main()
{
int i, n, a[25];
printf("Enter total a of elements:\n ");
scanf("%d",&n);
printf("Enter elements:\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
Output:
quicksort(a,0,n-1); Enter total a of elements:
printf("The Sorted elements are:\n "); 5
Enter elements:
for(i=0;i<n;i++) 50 30 40 20 10
printf(" %d",a[i]); The Sorted elements are:
10 20 30 40 50
return 0;
}
END

You might also like