Lab 01

Green University of Bangladesh
Department of Computer Science and Engineering(CSE)

Faculty of Sciences and Engineering
Semester: (Fall, Year:2022), B.Sc. in CSE (Day)
LAB REPORT NO 01
Course Title: Algorithms Lab
Course Code: CSE 206 Section:D1
Lab Experiment Name: Implementation of merge sort and quick sort.
Student Details
Name ID
1. Md Abdullah Talukdar 212002014
Lab Date:24-10-2022
Submission Date: 31-10-2022
Course Teacher’s Name : Tanoy Debnath
[For Teachers use only: Don’t Write Anything inside this box]
Lab Report Status

Marks: ………………………………… Signature:.....................
Comments:.............................................. Date:..............................
1. TITLE OF THE LAB EXPERIMENT
Implementation of merge sort and quick sort .
2. OBJECTIVES/AIM
Merge Sort
In the merge sort, the array is parted into just 2 halves (i.e. n/2).
It operates fine on any size of array.
It has a consistent speed on any size of data.
Quick Sort
The splitting of an array of elements is in any ratio, not necessarily divided into half.
It works well on smaller arrays.
It works faster than other sorting algorithms for small data sets like Selection sort
etc.
3. PROCEDURE / ANALYSIS / DESIGN

Merge Sort Algorithm
step 1: start
step 2: declare array and left, right, mid variable
step 3: perform merge function.
if left > right
return
mid= (left+right)/2
mergesort(array, left, mid)
mergesort(array, mid+1, right)
merge(array, left, mid, right)
step 4: Stop
Quick Sort Algorithm
Step 1 - Consider the first element of the list as pivot (i.e., Element at first position in
the list).
Step 2 - Define two variables i and j. Set i and j to first and last elements of the list
respectively.
Step 3 - Increment i until list[i] > pivot then stop.
Step 4 - Decrement j until list[j] < pivot then stop.
Step 5 - If i < j then exchange list[i] and list[j].
Step 6 - Repeat steps 3,4 & 5 until i > j.
Step 7 - Exchange the pivot element with list[j] element.
4. IMPLEMENTATION
#include <stdio.h>
void mergesort();
void marge();
int main() {
int a [40],n,i;
printf("Enter Size of array::");
scanf("%d",&n);
printf("Enter Elements:::");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
mergesort(a,0,n-1);
printf("Sorted elements are::");

for(i=0;i<n;i++)
printf("%d",a[i]);
return 0;
}
void mergesort(int a[],int first,int last){
int mid;
if(first<last){
mid=(first+last)/2;
mergesort(a,first,mid);
mergesort(a,mid+1,last);
marge(a,first,mid,last);
}
}
void marge(int a[],int first,int mid,int last){

int b[50];
int i,j,k;
i=first;
j=mid+1;
k=first;
while(i<=mid&&j<=last){
if(a[i]<=a[j])
b[k++]=a[i++];
else
b[k++]=a[j++];
}
if(i>mid){
while (j<=last)
b[k++]=a[j++];
}
else
{
while (i<=mid)
b[k++]=a[i++];
}
for(i=first;i<=last;i++)
a[i]=b[i];
}
#include <stdio.h>
void quiksort(int a[40],int first,int last)

{
int i,j,p,temp;
if (first<last)
{
p=first;
i=first;
j=last;
while(i<j)
{
while(a[i]<=a[p]&&i<last)
i++;
while(a[j]>a[p])
j--;
if(i<j){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[p];
a[p]=a[j];
a[j]=temp;
quiksort(a,0,j-1);
quiksort(a,j+1,last);
}
}
int main()
{
int a[40],n,i;
printf("Enter size of arr::");
scanf("%d",&n);
printf("Enter Elements:::");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
quiksort(a,0,n-1);
printf("Sortrd Elements are::");

for(i=0;i<n;i++)
printf("%d",a[i]);
return 0;
}
5. TEST RESULT / OUTPUT

6. ANALYSIS AND DISCUSSION
Although both merge sort and quicksort work on the same divide-and-conquer principle,
they handle the partition and sorting very differently.
Merge sort partitions a list into two sublists of equal sizes (different in size by 1, when
the size of the list is odd) and merges the sorted sublists optimally to form a sorted list.
In contrast, quicksort doesn’t necessarily partition the list into sublists of equal size. The
partition sizes may be of any size, depending on how we choose the pivot.
We can also observe that merge sort performs all the sorting during the process of
merging while quicksort performs most of the sorting in the process of dividing.

Lab 01

Uploaded by

Copyright:

Available Formats

Lab 01

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lab 01

Uploaded by

Copyright:

Available Formats

Green University of Bangladesh

Department of Computer Science and Engineering(CSE)

Lab Experiment Name: Implementation of merge sort and quick sort.

1. Md Abdullah Talukdar 212002014

Lab Report Status

Implementation of merge sort and quick sort .

3. PROCEDURE / ANALYSIS / DESIGN

Step 3 - Increment i until list[i] > pivot then stop.

Step 4 - Decrement j until list[j] < pivot then stop.

Step 5 - If i < j then exchange list[i] and list[j].

Step 6 - Repeat steps 3,4 & 5 until i > j.

Step 7 - Exchange the pivot element with list[j] element.

printf("Sorted elements are::");

void marge(int a[],int first,int mid,int last){

void quiksort(int a[40],int first,int last)

printf("Sortrd Elements are::");

5. TEST RESULT / OUTPUT

Merge Sort Algorithm

6. ANALYSIS AND DISCUSSION

You might also like