Question

a) 70 marks] Write a program that Sorts a given integer array via Selection Sort obtained by rotation around 3. Searches for a key point in the rotated array in O(logn) time, where the rotation Rotates the sorted array around a random point, e.g., 1 2 345->34512 is point is known in advance. ts above by first finding the unknown rotation point via sequential search and binary search (you forget the random rotation point and re-compute it). b) 130 marks] Find the recurrence relation, T(n), for the running time of ysf (n). Do not forget to include a base case T(0). Write the relation, do not try to solve it. int ysf (int n) i int res; if (n > 0) res- ysf (n-4) return res; 5*ysf (n/2) +2 else return li

PLEASE write in C Language, ( you can use array, recursive function, Pointers, Dynamic call by refernce, Structure)

Answer 1

if you have any further queries please feel free to ask

a) /////////////////program to sort array using selection sort in C/////////////

Write a program that Sorts a given integer array using Selection Sort

#include <stdio.h>

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void selectionSort(int data[], int n)
{
    int i, j, index;
    for (i = 0; i < n-1; i++)
    {
        // Find the minimum element in unsorted array
        index = i;
        for (j = i+1; j < n; j++)
          if (data[j] < data[index])
            index = j;

        // Swap the minimum element with the first element
        swap(&data[index], &data[i]);
    }
}

// main program to test above functions
int main()
{   int n,i;
    int arr[30];
    printf("enter the no: of elements: \n");
    scanf("%d",&n);
    printf("enter the elements: \n");
    for(i=0;i<n;i++)
    scanf("%d",&arr[i]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
    for (i=0; i < n; i++)
    printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

4 5 3 2 1 19 22 0 2 3 Smain enter the no: of elements: enter the elements: Sorted array: 0 1 2 2 334 5 19 22

/////////////////////////////////////////////////

b) rotate the sorted array around a random point

#include <stdio.h>

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void selectionSort(int data[], int n)
{
    int i, j, index;
    for (i = 0; i < n-1; i++)
    {
        // Find the minimum element in unsorted array
        index = i;
        for (j = i+1; j < n; j++)
          if (data[j] < data[index])
            index = j;

        // Swap the minimum element with the first element
        swap(&data[index], &data[i]);
    }
}

/* Function to print an array */
void print(int data[], int s)
{
    int i;
    for (i=0; i < s; i++)
        printf("%d ", data[i]);
    printf("\n");
}

/* rotate array to left of size n by d*/
void leftRotate(int arr[], int d, int n)
{
    int i;
    for (i = 0; i < d; i++)
        {
          int temp = arr[0], i;
          for (i = 0; i < n - 1; i++)
          arr[i] = arr[i + 1];
         arr[i] = temp;
        }
      
}

// main program to test above functions
int main()
{   int n,i,pos;
    int arr[30];
    printf("enter the no: of elements: \n");
    scanf("%d",&n);
    printf("enter the elements: \n");
    for(i=0;i<n;i++)
    scanf("%d",&arr[i]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
   print(arr, n);
   printf("enter the position of element from the sorted list where rotation is needed: \n");
   scanf("%d",&pos);
   leftRotate(arr, pos, n);

   print(arr, n);
    return 0;
}

Sgcc-o main .C Şmain enter the no: of elements: 10 enter the elements: 4 5 3 2 1 19 22 0 2 3 Sorted array: 0 1 2 2 334 5 19 22 enter the position of element from the sorted list where rotation is needed:7 5 19 22 0 1 2 2 3 3 4

c) Searches for a key point in the rotated array in O(logn) time, where the rotation point is known in advance

to search in O(logn) we can use binary search since the array is sorted

program to perform selection sort,rotate the sorted array and search element from the sorted array using binary search which is of order O(logn)

#include <stdio.h>

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void selectionSort(int data[], int n)
{
    int i, j, index;
    for (i = 0; i < n-1; i++)
    {
        // Find the minimum element in unsorted array
        index = i;
        for (j = i+1; j < n; j++)
          if (data[j] < data[index])
            index = j;

        // Swap the minimum element with the first element
        swap(&data[index], &data[i]);
    }
}



/* Function to print an array */
void print(int data[], int s)
{
    int i;
    for (i=0; i < s; i++)
        printf("%d ", data[i]);
    printf("\n");
}

/*Function to left rotate arr[] of size n by d*/
void leftRotate(int arr[], int d, int n)
{
    int i;
    for (i = 0; i < d; i++)
        {
          int temp = arr[0], i;
          for (i = 0; i < n - 1; i++)
          arr[i] = arr[i + 1];
         arr[i] = temp;
        }
      
}

int search(int arr[], int l, int h, int key)
{
    if (l > h) return -1;

    int mid = (l+h)/2;
    if (arr[mid] == key) return mid;

    /* If arr[l...mid] is sorted */
    if (arr[l] <= arr[mid])
    {
        /* As this subarray is sorted, we can quickly
        check if key lies in half or other half */
        if (key >= arr[l] && key <= arr[mid])
        return search(arr, l, mid-1, key);

        return search(arr, mid+1, h, key);
    }

    if (key >= arr[mid] && key <= arr[h])
        return search(arr, mid+1, h, key);

    return search(arr, l, mid-1, key);
  
}

// main program to test above functions
int main()
{   int n,i,j,pos,key;
    int arr[30];
    printf("enter the no: of elements: \n");
    scanf("%d",&n);
    printf("enter the elements: \n");
    for(i=0;i<n;i++)
    scanf("%d",&arr[i]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
   print(arr, n);
   printf("enter the position of element from the sorted list where rotation is needed: \n");
   scanf("%d",&pos);
   leftRotate(arr, pos, n);

   print(arr, n);
   printf("enter the element to be searched: \n");
   scanf("%d",&key);
   j = search(arr, 0, n-1, key);

    if (j != -1)
   printf("Index of the element is : %d", j);
   else
   printf("Index of the element is not found");

    return 0;
}

Smain enter the no: of elements: 1O enter the elements: Sorted array: 0 1 2 2 33 4 5 19 22 enter the position of element from the sorted list where rotation is needed: 6 4 5 19 22 01 2 2 3 3 enter the element to be searched: 1 Index of the element is:5 4 5 3 2 119 22 0 2 3

d) Repeat above by first finding the unknown rotation point via sequential search and binary search (you forget the random rotation point and re-compute it)

#include <stdio.h>

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void selectionSort(int data[], int n)
{
    int i, j, index;
    for (i = 0; i < n-1; i++)
    {
        // Find the minimum element in unsorted array
        index = i;
        for (j = i+1; j < n; j++)
          if (data[j] < data[index])
            index = j;

        // Swap the minimum element with the first element
        swap(&data[index], &data[i]);
    }
}



/* Function to print an array */
void print(int data[], int s)
{
    int i;
    for (i=0; i < s; i++)
        printf("%d ", data[i]);
    printf("\n");
}

/*Function to left rotate arr[] of size n by d*/
void leftRotate(int arr[], int d, int n)
{
    int i;
    for (i = 0; i < d; i++)
        {
          int temp = arr[0], i;
          for (i = 0; i < n - 1; i++)
          arr[i] = arr[i + 1];
         arr[i] = temp;
        }
      
}

int search(int arr[], int l, int h, int key)
{
    if (l > h) return -1;

    int mid = (l+h)/2;
    if (arr[mid] == key) return mid;

    /* If arr[l...mid] is sorted */
    if (arr[l] <= arr[mid])
    {
        /* As this subarray is sorted, we can quickly
        check if key lies in half or other half */
        if (key >= arr[l] && key <= arr[mid])
        return search(arr, l, mid-1, key);

        return search(arr, mid+1, h, key);
    }

    if (key >= arr[mid] && key <= arr[h])
        return search(arr, mid+1, h, key);

    return search(arr, l, mid-1, key);
  
}

// main program to test above functions
int main()
{   int n,i,j,element,pos,key;
    int arr[30];
    printf("enter the no: of elements: \n");
    scanf("%d",&n);
    printf("enter the elements: \n");
    for(i=0;i<n;i++)
    scanf("%d",&arr[i]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
   print(arr, n);
   printf("enter the element from the sorted list where rotation is needed: \n");
   scanf("%d",&element);
   //sequential search to find the position of the element in the sorted array
   for(i=0;i<n;i++)
   {
   if(arr[i]== element)
   pos=i;
   }
   leftRotate(arr, pos, n);

   print(arr, n);
   printf("enter the element to be searched: \n");
   scanf("%d",&key);
   j = search(arr, 0, n-1, key);

    if (j != -1)
   printf("Index of the element is : %d", j);
   else
   printf("Index of the element is not found");

    return 0;
}

T

Smain enter the no: of elements 10 enter the elements: 45 3 2 1 19 22 0 2 3 Sorted array: 0 1 2 2 33 4 5 19 22 enter the element from the sorted list where rotation is needed:19 19 22 01 2 2 33 4 5 enter the element to be searched: 1 Index of the element is3