Scribd
Upload
72 views4 pages

DSA Assignment #3 LAB

The document contains code and explanations for merge sort and quick sort algorithms. It includes code to implement merge sort using a helper merge function, code to implement quick sort using a partition and swap function, and an explanation of why quick sort is generally considered better than merge sort despite merge sort having better worst case time complexity. The key reasons given are that quick sort has less auxiliary space requirements, avoids worst cases more easily with randomized pivots, and has better cache locality.

Uploaded by

Top10 EveryThing
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
72 views4 pages

DSA Assignment #3 LAB

The document contains code and explanations for merge sort and quick sort algorithms. It includes code to implement merge sort using a helper merge function, code to implement quick sort using a partition and swap function, and an explanation of why quick sort is generally considered better than merge sort despite merge sort having better worst case time complexity. The key reasons given are that quick sort has less auxiliary space requirements, avoids worst cases more easily with randomized pivots, and has better cache locality.

Uploaded by

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

DSA

ASSIGNMENT #3

LAB

Q1
MERGE SORT

#include <iostream>
using namespace std;
void merge(int *, int *, int, int, int);
void mergesort(int *a, int *b, int low, int high)
{
int pivot;
if (low < high)
{
pivot = (low + high)/2;
mergesort(a, b, low, pivot);
mergesort(a, b, pivot + 1, high);
merge(a, b, low, pivot, high);
}
}
void merge(int *a, int *b, int low, int pivot, int high)
{
int h, i, j, k;
h = low;
i = low;
j = pivot + 1;

while ((h <= pivot) && (j <= high))


{
if (a[h] <= a[j])
{
b[i] = a[h];
h++;
}
else
{
b[i] = a[j];
j++;
}
i++;
}
if (h > pivot)
{
for (k = j; k <= high; k++)
{
b[i] = a[k];
i++;
}
}
else
{
for (k = h; k <= pivot; k++)
{
b[i] = a[k];
i++;
}
}
for (k = low; k <= high; k++) a[k] = b[k];
}
int main()
{
int a[] = {3,7,1,9,11,24,6 };
int num;

num = sizeof(a)/sizeof(int);

int b[num];
mergesort(a, b, 0, num-1);

for (int i = 0; i < num; i++)


cout << a[i] << " ";
cout << endl;
}
Q2
#QUICK SORT#

#include <iostream>
using namespace std;

void swap(int *a,int *b)


{
int temp = *a;
*a=*b;
*b = temp;
}
int partition (int A[], int p, int r)
{
int x = A[r];
int i = p - 1;

for (int j = p; j <= r- 1; j++)


{
if (A[j] <= x)
{
i++;
swap (&A[i], &A[j]);
}
}
swap (&A[i + 1], &A[r]);
return (i + 1);
}
void quickSort(int A[], int p, int r)
{
if (p < r)
{
int q = partition(A, p,r);
quickSort(A, p, q - 1);
quickSort(A, q + 1, r);
}
}
int main()
{
int a[] = {3,7,1,9,11,24,6 };
int n = sizeof(a)/sizeof(a[0]);
quickSort(a,0,n-1);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}

Q#3

This a common question asked in DS interviews that despite of better worst


case performance of mergesort, quicksort is considered better than mergesort.
There are certain reasons due to which quicksort is better especially in case of
arrays: 
1. Auxiliary Space : Mergesort uses extra space, quicksort requires little
space and exhibits good cache locality. Quick sort is an in-place sorting
algorithm. In-place sorting means no additional storage space is needed to
perform sorting. Merge sort requires a temporary array to merge the sorted
arrays and hence it is not in-place giving Quick sort the advantage of space.
2. Worst Cases : The worst case of quicksort O(n2) can be avoided by
using randomized quicksort. It can be easily avoided with high probability by
choosing the right pivot. Obtaining an average case behavior by choosing
right pivot element makes it improvise the performance and becoming as
efficient as Merge sort.
3. Locality of reference : Quicksort in particular exhibits good cache
locality and this makes it faster than merge sort in many cases like in virtual
memory environment.
4. Merge sort is better for large data structures: Mergesort is a stable
sort, unlike quicksort and heapsort, and can be easily adapted to operate on
linked lists and very large lists s

You might also like