MERGE SORT & QUICK

SORT
“Deloit”, a software company needs to store its employee details like
employee id, name, address etc in a record, develop a program in C to sort
the employee records based on their employee ID by using merge sort
methodology, employee ID should be generated randomly. Determine the
time required to sort the elements. Repeat the experiment for different
values of n and plot a graph of the time taken versus n. (n=no of elements).
 Aim: To sort given set of elements using merge sort & calculating the time taken to sort.

 Theory: Merge sort sorts a given array A[0...n-1] by dividing it in to two halves A[0...[n/2]-1]
and sorted A[[n/2]...n-1],sorting each of them recursively, and then merge the two smaller sorted
arrays into a single one.
Conceptually, a merge sort works as follows:
1.If the list is of length 0 or 1, then it is already sorted.
Otherwise:
2.Divide the unsorted list into two sub lists of about half the size.
3.Sort each sub lists recursively by re-applying merge sort.
4.Merge the two sub lists back into one sorted list.
 ALGORITHM MergeSort (a, 0, n-1)
if(low < high)
mid = (low+high)/2 // Divide the array into equal
parts
MergeSort(a,low,mid) // Sort the left part of the array recursively
MergeSort(a,mid+1,high) // Sort the right part of the array recursively
SimpleMerge(a,low,mid,high) // Merge the left part and right part
end if
 SimpleMerge(a, low, mid, high)
i  low, j mid+1, k  low
while ( i <= mid and j <= high)
If ( A[i] < A[j] ) then
C[k]  A[i] // Copy the lowest element from first part of A to C
i  i+1 // Point to next item in the left part of A
k  k+1 // Point to next item in C
else
C[k]  A[j] // Copy the lowest element from 2nd part of A to C
j  j+1 //Point to next item in the second part of A
k  k+1 //Point to next item in C
end if
end while
while ( i <= mid) // Copy the remaining items from left part of A to C
C[k]  A[i]
k  k+1, i  i + 1
end while
while ( j <= high) // Copy the remaining items from right part of A to C
C[k]  A[j]
k  k + 1, j  j + 1
end while
for i = low to high //Copy the elements from vector C to vector A
a[i]  c[i]
end for
return // End of the algorithm
 SimpleMerge(a, low, mid, high)
while ( i <= mid) // Copy the remaining items from left part of A to C
i  low, j mid+1, k  low
C[k]  A[i]
while ( i <= mid and j <= high)
k  k+1, i  i + 1
If ( A[i] < A[j] ) then
end while
C[k]  A[i] // Copy
the lowest element while ( j <= high) // Copy the remaining items from right part of A to C
from first part of A to C
C[k]  A[j]
i  i+1 // Point to
next item in the k  k + 1, j  j + 1
left part of A end while
k  k+1 // Point to for i = low to high //Copy the elements from vector C to vector A
next item in C
a[i]  c[i]
else
end for
C[k]  A[j] // Copy
the lowest element return // End of the algorithm
from 2nd part of A to C

j  j+1 //Point to
next item in the
second part of A

k  k+1 //Point to
next item in C

end if

end while
FUNCTIONS
void merge(int,int,int);
void merge_sort(int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(low,mid);
merge_sort(mid+1,high);
merge(low,mid,high);
}
}
void merge(int low ,int mid ,int high)
if(h>mid)
{
{
int h ,I , j, b [500000],k;
for(k=j; k<=high ; k++)
h=low;
{
i=low;
b[i]=a[k];
j=mid+1; i++;
while((h<=mid)&&(j<=high)) }
{ }
if(a[h]<=a[j]) else
{ {
b[i]=a[h]; for(k=h ; k<=mid ; k++)
h++; {
} b[i]=a[k];
else i++;
{ }
b[i]=a[j]; }
j ++; for(k=low; k<=high; k++)
a[k]=b[k];
}
}
i++;
}
 Expected output:
Enter the number of employee records: 5

The Employee IDs are:

62 34 50 28 16

Employee IDs in sorted order:

16 28 34 50 62

The time taken is 0.989011

QUICK SORT

Assume that NMIT college needs to maintain the student details like USN, name,
and contact details in a record. USN should be generated randomly. Design and
develop a program in C to sort the records based on USN by using quick sort
algorithm. Determine the time required to sort the roll numbers. Repeat the
experiment for different values of n and plot a graph of the time taken versus n.
(n=no of elements).
 Aim: To sort given set of elements using Quick sort and to find the time required to sort the
elements.

 Theory: Quick sort divides its inputs elements according to their value. It rearranges elements
of a given array A[0...n-1] to achieve its partition a situation where all the elements before some
positions are smaller than or equal to A[s] and all the elements after position S are greater than
or equal to A[s]. After partition is achieved a[s] will be in its final position in the sorted array. And
we can continue sorting the two sub arrays of the elements preceding and following A[s]
independently.
 Quick sort sorts by employing a divide and conquer strategy to divide a list into two sub - lists.

 The Steps are:

1. Pick an element, called a pivot, from the list.

2. Reorder the list so that all elements, which are less than the pivot, come before the pivot and so that
all elements greater than the pivot come after it (equal values can go either way). After this
partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively sorts the sub-list of lesser elements and the sub-list of greater elements.
ALGORITHM QuickSort(a, low, high)

if(low < high)

mid = partition(a,low,high) //divide the array into equal parts

quick_sort(a,low,mid-1) //sort the left part of the array

quick_sort(a,mid+1,high) //sort the right part of the array

end if

Partition(a, low, high)

key  a[low] // The key element also called pivot element

i  low; // Points to the first element in the array

j  high + 1 //Points to the last element in the array

While (i <= j)

do i  i +1 while (key >= a[i] // If sentinel is present at the end of the array

//If sentinel is not present change as shown

// do i  i + 1 while (i <= high && key >= a[i])

do j  exchange ( a[i], a[j])

if (i < j) exchange (a[i], a[j])

end while

exchange (a[j], a[low])

return j
FUNCTIONS
int partition(int a[],int low,int high) if(i<j)

{ {
temp=a[i];
int i,j,temp,pivot;
a[i]=a[j];
pivot=a[low];
a[j]=temp;
i=low+1;
}
j=high;
else
while(1) {
{ temp=a[j];
a[j]=a[low];
while(i<high&&a[i]<=pivot) a[low]=temp;
i++; return j;
while(a[j]>pivot) }

j--; }
}
quick_sort(int a[],int low,int high)
{
int j;
if(low<high)
{
j=partition(a,low,high);
quick_sort(a,low,j-1);
quick_sort(a,j+1,high);
}
}
Expected output:

Enter the number of students records: 5

The roll numbers are:

62 34 50 28 16

Sorted roll numbers are:

16 28 34 50 62

The time taken to sort is 0.93454336