EXPERIMENT NUMBER: 1
Date of Performance :
Date of Submission :
Aim: Implement Merge sort and Quicksort for the given list of integer values and
find space and time complexity.
Theory:
A divide and conquer algorithm is a problem-solving approach where a large problem
is broken down into smaller, more manageable subproblems, which are then solved
recursively. So, divide and conquer Algorithm is used to solve problems by
dividing the main problem into subproblems, solving them individually and then
merging them to find solution to the original problem. Divide and Conquer is mainly
useful when we divide a problem into independent subproblems.
Key steps involved in a divide and conquer algorithm:
1. Divide: The original problem is divided into smaller subproblems of the same type.
2. Conquer: The subproblems are solved recursively. If the subproblems are small
enough, they are solved directly (base case).
3. Combine: The solutions of the subproblems are combined to form the solution of the
original problem.
Examples of divide and conquer algorithms:
Merge Sort:
This algorithm sorts a list by dividing it into two halves, recursively sorting each half,
and then merging the two sorted halves.
Quick Sort:
This algorithm selects a "pivot" element and partitions the array around it, then
recursively sorts the sub-arrays.
Binary Search:
This algorithm efficiently searches a sorted array by repeatedly dividing the search
interval in half.
Advantages of divide and conquer:
● Parallelism:
The subproblems can often be solved in parallel, leading to further performance
improvements.
● Clarity:
The recursive nature of the algorithm can make the logic easier to understand and
implement.
Disadvantages of divide and conquer:
● Stack Overflow:
Recursive calls can lead to stack overflow errors if the recursion is too deep.
● Overhead:
The overhead of dividing and combining the solutions can sometimes outweigh the
benefits of recursion.
Merge Sort:
Merge Sort is one of the most popular sorting algorithms that is based on the principle
of Divide and Conquer Algorithm.
Here, a problem is divided into multiple sub-problems. Each sub-problem is solved
individually. Finally, sub-problems are combined to form the final solution. i.e. In this
sorting algorithm the unsorted array keeps on dividing into two halves until the array is
either empty or contains only one element, which is the base case of Merge Sort, and then
the halves are combined/Merged in sorted order producing a sorted array.
Example:
If the input array is {7, 2, 3, 10, 1, 0, 6, 9}
the expected output array will have data as {0, 1, 2, 3, 6, 7, 9, 10}
How Merge Sort Works:
● Divide: The algorithm recursively divides the unsorted array into two halves until each
sub-array contains only one element. A single-element array is inherently sorted.
● Conquer: Each of these single-element sub-arrays is considered sorted.
● Combine (Merge): The sorted sub-arrays are then merged back together in a sorted
manner. This merging process is crucial: it takes two sorted sub-arrays and combines
them into a single, larger sorted array. This merging continues upwards until the entire
original array is sorted.
Program:
// C program for the implementation of merge sort
#include <stdio.h>
#define max 10
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44,
0 }; int b[10];
void merging(int low, int mid, int high)
{ int l1, l2, i;
for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
if(a[l1] <= a[l2])
b[i] = a[l1++];
else
b[i] = a[l2++];
}
while(l1 <= mid)
b[i++] = a[l1++];
while(l2 <= high)
b[i++] = a[l2++]; for(i
= low; i <= high; i++)
a[i] = b[i];
}
void sort(int low, int high){
int mid; if(low < high)
{ mid = (low + high) /
2; sort(low, mid);
sort(mid+1, high);
merging(low, mid, high);
} else {
return;
}
}
int main(){
int i;
printf("Array before sorting\
n"); for(i = 0; i <= max; i++)
printf("%d ", a[i]); sort(0,
max);
printf("\nArray after sorting\
n"); for(i = 0; i <= max; i++)
printf("%d ", a[i]);
}
Key Characteristics:
● Time Complexity: O(n log n) in all cases (best, average, and worst), making it very
efficient for large datasets.
● Space Complexity: O(n) due to the use of temporary arrays during the merge
operation.
● Stability: Merge sort is a stable sorting algorithm, meaning it preserves the relative
order of equal elements.
OUTPUT:
Array before sorting
10 14 19 26 27 31 33 35 42 44 0
Array after sorting
0 10 14 19 26 27 31 33 35 42 44
QUICKSORT:
QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and
partitions the given array around the picked pivot. There are many different versions
of quickSort that pick pivot in different ways.
1. Always pick first element as pivot.
2. Always pick last element as pivot (implemented below)
3. Pick a random element as pivot.
4. Pick median as pivot.
The key process in quickSort is partition(). Target of partitions is, given an array and
an element x of array as pivot, put x at its correct position in sorted array and put all
smaller elements (smaller than x) before x, and put all greater elements (greater than
x) after x. All this should be done in linear time.
Program:
/*
C Program to Perform Quick Sort on a set of Entries from a File
using Recursion
*/
#include <stdio.h>
void quicksort (int [], int, int);
int
main() {
int
list[50];
int size, i;
printf("Enter the number of elements: ");
scanf("%d", &size); printf("Enter the
elements to be sorted:\n");
for (i = 0; i < size; i++)
{
scanf("%d", &list[i]);
}
quicksort(list, 0, size - 1);
printf("After applying quick sort\n");
for (i = 0; i < size; i++)
{
printf("%d ", list[i]);
}
printf("\n");
return 0;
} void quicksort(int list[], int low,
int high)
{ int pivot, i, j,
temp;
if (low < high)
{
pivot = low;
i = low;
j = high;
while (i < j)
{
while (list[i] <= list[pivot] && i <= high)
{
i++;
}
while (list[j] > list[pivot] && j >= low)
{ j--;
} if (i < j)
{ temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
temp = list[j];
list[j] = list[pivot];
list[pivot] = temp;
quicksort(list, low, j - 1);
quicksort(list, j + 1, high);
}
}
Output:
Enter the number of elements: 6
Enter the elements to be sorted:
67
45
24
98
12
38
After applying quick sort
12 24 38 45 67 98
Analysis of Quicksort:
It has an average and best-case time complexity of O(n log n), making it a fast
sorting method for large datasets. However, its worst-case time complexity is
O(n^2), which can occur with poorly chosen pivots. The space complexity is
typically O(log n)
CONCLUSION : Thus we have studied the concept of Divide and Conquer strategy.
SIGN and REMARK :
R1 (3 M) R2 (3 M) R3 (3 M) R4 (3 M) R5(3 M) TOTAL MARKS SIGNATURE
(15)
-----------------------------------------------------------------------------------------------------------------------