1.MERGE AND QUICK SORT

PHOTO EMBED

Sun Nov 03 2024 12:40:56 GMT+0000 (Coordinated Universal Time)

Saved by @varuntej #c 

Task-1
a) Implement Merge sort algorithm and plot its time complexity with reference to the size of the input.
Algorithm:
Algorithm MergeSort(low, high)
// a[low : high] is a global array to be sorted.
// Small(P) is true if there is only one element
// to sort. In this case the list is already sorted.
{
    if (low < high) then     // If there are more than one element
    {
        // Divide P into subproblems.
        // Find where to split the set.
        mid := ⌊(low + high) / 2⌋;
        // Solve the subproblems.
        MergeSort(low, mid);
        MergeSort(mid + 1, high);
        // Combine the solutions.
        Merge(low, mid, high);
    }
}
Algorithm Merge(low, mid, high)
// a[low : high] is a global array containing two sorted
// subsets in a[low : mid] and in a[mid + 1 : high]. The goal
// is to merge these two sets into a single set residing
// in a[low : high]. b[ ] is an auxiliary global array.
{
  h := low; i := low; j := mid + 1;
  while ((h ≤ mid) and (j ≤ high)) do
  {
    if (a[h] ≤ a[j]) then
    {
      b[i] := a[h]; h := h + 1;
    }
    else
    {
      b[i] := a[j]; j := j + 1;
    }
    i := i + 1;
  }
  if (h > mid) then
    for k := j to high do
    {
      b[i] := a[k]; i := i + 1;
    }
  else
    for k := h to mid do
    {
      b[i] := a[k]; i := i + 1;
    }
  for k := low to high do a[k] := b[k];
}

Program:
#include <stdio.h>
#include <time.h>
void merge(int a[],int i1,int j1,int i2,int j2) {
	int i,j,k=0;
	i=i1;
	j=i2;
	int temp[100];
	while(i<=j1 && j<=j2) {
		if(a[i]<a[j])
			temp[k++]=a[i++];
		else
			temp[k++]=a[j++];
	}
	while(i<=j1)
		temp[k++]=a[i++];
	while(j<=j2)
		temp[k++]=a[j++];
	for(i=i1,j=0; i<=j2; i++,j++)
		a[i]=temp[j];
}
void partition(int a[],int l,int h) {
	if(l<h) {
		int mid=(l+h)/2;
		partition(a,l,mid);
		partition(a,mid+1,h);
		merge(a,l,mid,mid+1,h);
	}
}
int main() {
	int n;
	printf("enter the size of array: ");
	scanf("%d",&n);
	int a[n];
	for(int i=0; i<n; i++)
		a[i] = n - i;
	clock_t t = clock();
	partition(a,0,n-1);
	t = clock() - t;
	printf("Time taken: %f \n",((float)t*1000)/CLOCKS_PER_SEC);
	for(int i=0; i<n; i++)
		printf("%d ",a[i]);
	return 0;
}
Output:
enter the size of array: 5
Time taken: 0.002000 
1 2 3 4 5 

=== Code Execution Successful ===
b) Implement Quick sort algorithm and plot its time complexity regarding asymptotic notations (Best, average, and worst).
Algorithm:
Algorithm QuickSort(p, q)
// Sorts the elements a[p], ..., a[q] which reside in the global
// array a[1 : n] into ascending order; a[n + 1] is considered to
// be defined and must be ≥ all the elements in a[1 : n].
{
    if (p < q) then     // If there are more than one element
    {
        // divide P into two subproblems.
        j := Partition(a, p, q + 1);
        // j is the position of the partitioning element.
        // Solve the subproblems.
        QuickSort(p, j - 1);
        QuickSort(j + 1, q);
        // There is no need for combining solutions.
    }
}
Algorithm Partition(a, m, p)
// Within a[m], a[m + 1], ..., a[p − 1] the elements are
// rearranged in such a manner that if initially t = a[m],
// then after completion a[q] = t for some q between m
// and p − 1, a[k] ≤ t for m ≤ k < q, and a[k] ≥ t
// for q < k < p. q is returned. Set a[p] = ∞.
{
  v := a[m]; i := m; j := p;
  repeat
  {
    repeat
      i := i + 1;
    until (a[i] ≥ v);
    
    repeat
      j := j − 1;
    until (a[j] ≤ v);
    
    if (i < j) then Interchange(a, i, j);
  } until (i ≥ j);
  
  a[m] := a[j]; a[j] := v; return j;
}

Algorithm Interchange(a, i, j)
// Exchange a[i] with a[j].
{
  p := a[i];
  a[i] := a[j]; a[j] := p;
}

Program:
#include <stdio.h>
#include <time.h>

void quicksort(int number[25], int first, int last) {
    int i, j, pivot, temp;
    if (first < last) {
        pivot = first;
        i = first;
        j = last;
        while (i < j) {
            while (number[i] <= number[pivot] && i < last)
                i++;
            while (number[j] > number[pivot])
                j--;
            if (i < j) {
                temp = number[i];
                number[i] = number[j];
                number[j] = temp;
            }
        }
        temp = number[pivot];
        number[pivot] = number[j];
        number[j] = temp;
        quicksort(number, first, j - 1);
        quicksort(number, j + 1, last);
    }
}

int main() {
    int i, count, number[25];
    printf("SIZE OF ARRAY?: ");
    scanf("%d", &count);

    printf("Enter array elements: ");
    for (i = 0; i < count; i++) {
        scanf("%d", &number[i]);
    }

    clock_t t = clock(); // Start time
    quicksort(number, 0, count - 1);
    t = clock() - t; // End time

    printf("Time taken: %f ms\n", ((float)t * 1000) / CLOCKS_PER_SEC);
    printf("Sorted elements:");
    for (i = 0; i < count; i++) {
        printf(" %d", number[i]);
    }
    printf("\n");

    return 0;
}
Output:

SIZE OF ARRAY?: 5
Enter array elements: 5 4 3 2 1
Time taken: 0.002000 ms
Sorted elements: 1 2 3 4 5


=== Code Execution Successful ===
content_copyCOPY