Chittagong Independent University
School of Science and Engineering (SSE)
Dept of Computer Science and Engineering (CSE)
Course Title : Algorithm Design and Analysis Lab
Course Code : CSE305L
Report No : 02
Name of the Report : Implementation of Merge Sort, Quick Sort Algorithm &
Maximum Sub-Array Problem
Experiment Date : 06-02-2024
Submission Date :
Submitted By:
Name : Ratul
ID : 22102018
Semester : Autumn 24’
Remarks:
Submitted To:
Dr. Sajjatul Islam
Assistant Professor
School of Science and Engineering, CIU
Page |2
Problem Statement
Implementation of Merge Sort, Quick Sort Algorithm also maximum sub array
Objectives
- To implement the concept of Merge Sort & Quick Sort algorithm.
- To analyse the maximum sub array problem.
Program Development Environment
- Codeblocks-20.03mingw IDE
- GCC-8.1.0 Compiler
- Operating system: Windows10 pro (64-bit)
Algorithmic Steps
Merge Sort:
If it is only one element in the list, consider it already sorted, so return.
Divide the list recursively into two halves until it can no more be divided.
Merge the smaller lists into new list in sorted order.
Quick Sort:
Choose the highest index value has pivot
Take two variables to point left and right of the list excluding pivot
Left points to the low index
Right points to the high
While value at left is less than pivot move right
While value at right is greater than pivot move left
If both step 5 and step 6 does not match swap left and right
If left ≥ right, the point where they met is new pivot
Maximum Sub-Array:
Divide the given array in two halves
Return the maximum of following three:
Maximum subarray sum in left half (Make a recursive call)
Maximum subarray sum in right half (Make a recursive call)
Maximum subarray sum such that the subarray crosses the midpoint
Page |3
Pseudocode:
Merge Sort Quick Sort
Maximum Sub-Array
Page |4
Time Complexity
Merge Sort: O(nlog(n)) Merge Sort is a recursive algorithm and time
complexity can be expressed as recurrence relation
Quick Sort:
1. Best Case: Ω (nlog(n))
2. Average Case: θ(nlog(n))
3. Worst Case: O(n2)
Maximum Sub-Array: O(nlog(n)) maxSubArraySum is a recursive method
and time complexity can be expressed as recurrence relation
Program Code
Merge Sort Algorithm
#include <stdio.h>
#include <stdlib.h>
void printArray(int A[], int n)
{
for (int i=0; i<n; i++)
{
printf("%d\t", A[i]);
}
printf("\n");
}
void merge(int A[], int mid, int low, int high)
{
int i, j, k, B[100];
i = low;
j = mid + 1;
k = low;
while (i <= mid && j <= high)
{
if (A[i] < A[j])
{
B[k] = A[i];
i++;
k++;
}
else
{
B[k] = A[j];
j++;
k++;
}
}
while (i <= mid)
{
B[k] = A[i];
k++;
i++;
}
while (j <= high)
Page |5
{
B[k] = A[j];
k++;
j++;
}
for (int i = low; i <= high; i++)
{
A[i] = B[i];
}
void mergeSort(int A[], int low, int high)
{
int mid;
if(low<high)
{
mid = (low + high)/2;
mergeSort(A, low, mid);
mergeSort(A, mid+1, high);
merge(A, mid, low, high);
}
}
int main()
{
int A[100], n;
printf("Number of elements : ");
scanf("%d", &n);
for(int i=0; i<n; i++)
{
printf("Enter element for [%d] : ", i);
scanf("%d", &A[i]);
}
printf("\n");
printf("Entered elements are : \n");
printArray(A, n);
printf("\n");
printf("Sorted Array after implementing Merge Sort: \n");
mergeSort(A, 0, n-1);
printArray(A, n);
return 0;
}
Quick Sort Algorithm
#include <stdio.h>
#include <stdlib.h>
int partition (int arr[], int low, int high)
{
int pivot = arr[low]; //pivot selection
int i = low+1;
int j = high;
int temp;
Page |6
while (i<=j)
{
while (arr[i] <= pivot)
{
i++;
}
while (arr[j] > pivot)
{
j--;
}
if (i<j)
{
// swap i & j!
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
//swap pivot & j!
temp = arr[low];
arr[low] = arr[j];
arr[j] = temp;
return j;
}
void quicksort(int arr[], int low, int high)
{
int loc;
if(low<high)
{
loc = partition(arr, low, high);
quicksort(arr, low, loc-1);
quicksort(arr, loc+1, high);
}
}
void display (int A[], int n)
{
for (int i=0; i<n; i++)
{
printf("%d\t", A[i]);
}
printf("\n");
}
int main()
{
int Arr[100], n;
printf("Number of elements : ");
scanf("%d", &n);
for(int i=0; i<n; i++)
{
printf("Enter element for [%d] : ", i);
scanf("%d", &Arr[i]);
}
Page |7
printf("\n");
printf("Entered elements are : \n");
display (Arr, n);
quicksort (Arr, 0, n-1);
printf("\n");
printf("Sorted Array after implementing Quick Sort: \n");
display(Arr, n);
return 0;
}
Maximum Sub-Array
#include <stdio.h>
#include <stdlib.h>
// Function to find the maximum of three integers
int max(int a, int b, int c)
{
return (a > b) ? ((a > c) ? a : c) : ((b > c) ? b : c);
}
// Function to find the maximum subarray crossing the middle point
int maxCrossingSum(int arr[], int low, int mid, int high)
{
int leftSum = INT_MIN;
int sum = 0;
// Traverse the left side of the middle point
for (int i = mid; i >= low; i--)
{
sum += arr[i];
if (sum > leftSum)
{
leftSum = sum;
}
}
int rightSum = INT_MIN;
sum = 0;
// Traverse the right side of the middle point
for (int i = mid + 1; i <= high; i++)
{
sum += arr[i];
if (sum > rightSum)
{
rightSum = sum;
}
}
// Return the sum of the maximum subarray crossing the middle point
return leftSum + rightSum;
}
// Function to find the maximum subarray using divide and conquer
int maxSubarraySum(int arr[], int low, int high)
{
Page |8
// Base case: If the array contains only one element, return it
if (low==high)
{
return arr[low];
}
// Find the middle point of the array
int mid = (low+high)/2;
// Recursively find the maximum subarray sum in the left and right
halves
int leftSum = maxSubarraySum(arr, low, mid);
int rightSum = maxSubarraySum(arr, mid+1, high);
// Find the maximum subarray sum crossing the middle point
int crossSum = maxCrossingSum(arr, low, mid, high);
// Return the maximum of the three sums
return max(leftSum, rightSum, crossSum);
}
void display (int A[], int n)
{
for (int i=0; i<n; i++)
{
printf("%d\t", A[i]);
}
printf("\n");
}
// Main function
int main()
{
int arr[100], n;
printf("Number of elements : ");
scanf("%d", &n);
for(int i=0; i<n; i++)
{
printf("Enter element for [%d] : ", i);
scanf("%d", &arr[i]);
}
printf("\n");
printf("Entered elements are : \n");
display (arr, n);
int result = maxSubarraySum(arr, 0, n-1);
printf("Maximum sub-array sum is %d\n", result);
return 0;
}
Page |9
Output
Merge Sort Algorithm
Quick Sort Algorithm
P a g e | 10
Max Sub-Array
Conclusion
In this lab, we implemented and explored the Merge Sort and Quick Sort algorithm for
sorting arrays in non-decreasing order. We also got knowledge about the time complexity of
those sorting algorithm.