Exercise 5.1. Consider the array S consisting of 8 elements in the following ord
ID: 3753298 • Letter: E
Question
Exercise 5.1. Consider the array S consisting of 8 elements in the following order: 8, 2, 6, 7, 5, 1, 4, 3. Find the total number of comparisons that each of the following algorithms takes on the below input:
a) Quicksort (Algorithm 15)
Algorithm 15 Algorithm QS(S). Input: A set S. Output: The set S in sorted order.
1: if |S| 6 1 then
2: return S
3: else
4: Let y be the first element in S.
5: Compare all elements of S to y.
Let
S1 = {x S {y} | x 6 y}
S2 = {x S {y} | x > y}.
(Elements in S1 and S2 are in the same order as in S.)
6: Return the list (in the following order): QS(S1), y, QS(S2)
b) MergeSort (Algorithm 12)
Algorithm 12 Algorithm Merge Sort(X, n)
1: MergeSort(X, 1, n)
Explanation / Answer
QuickSORT
#include<stdio.h>
void swp(int *x, int *y)
{
int z = *x;
*x = *y;
*y = z;
}
int mid (int arr[], int l, int h)
{
int pt = arr[h];
int i = (l - 1);
for (int j = l; j <= h - 1; j++)
{
if (arr[j] <= pt)
{
i++;
swp(&arr[i], &arr[j]);
}
}
swp(&arr[i + 1], &arr[h]);
return (i + 1);
}
void qSort(int arr[], int l, int h)
{
if (l < h)
{
int pi = mid(arr, l, h);
qSort(arr, l, pi - 1);
qSort(arr, pi + 1, h);
}
}
void main()
{
int array[] = {8, 2, 6, 7, 5, 1, 4, 3};
int n = sizeof(array)/sizeof(array[0]);
int i;
for(i=0;i<n-1;i++) {
if(array[i]<1){
printf("%d is less than 1",array[i]);
exit(-1);
}
}
qSort(array, 0, n-1);
for(i=0;i<n-1;i++)
printf("%d ",array[i]);
}
MERGESORT
#include<stdio.h>
void merge(int arr[], int l, int m, int r)
{
int i, j, k, n1,n2;
n1 = m - l + 1;
n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
k = l;
j = 0;
i = 0;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
void mSort(int arr[], int l, int r)
{
if (l < r)
{
int m = l+(r-l)/2;
mSort(arr, l, m);
mSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
void main()
{
int array[] = {12, 11, 13, 5, 6, 7},i;
int size = sizeof(array)/sizeof(array[0]);
mSort(array, 0, size - 1);
printf(" Sorted array is ");
for (i=0; i < size; i++)
printf("%d ", array[i]);
}