Question

Just Q3 and Q4

Q1] Write a C function to implement the binary search algorithm over an array of integer numbers and size n. The function should return the index of the search key if the search key exists and return - 1 if the search key doesn't exist. [10 Points] Q2] Write a C function to implement the selection sort algorithm, to sort an array of float values and size n. The function should sort the array in ascending order [10 Points). Q3) Write a C function using recursion to check if a given array of integer values of size n is a partially sorted array of degree m or not. The function IsPartiallySoreted will return 1 if the given array is an imperfect sorted array of degree less than or equal m and return of the imperfect degree is greater than m. [40 points] Given an array of n elements, where each element is at most m positions away from its target position if the array was sorted correctly, we call this array an imperfect sorted array of degreem NOTE: you may assume that all the values in the array are unique (no duplicates). Examples, Is the following array is an imperfect sorted array of degree 2 ? in other words, m - 2 0 1 2 3 4 5 6 7 3 7 8 109 12 14 11 17 20 YES: We can see that for a sorted array the values 9, 10, 12, 14, and 11 are not in their correct positions, however, to put any of them in its correct position we only need to move it at most 2 positions, for example, 11 will move from Array[7] to Array[5] and 10 will move from Array[3] to Array(4) Examples, The following array Is NOT an imperfect sorted array of degree 3, in other words, m - 3 10 11 51 2191 5 1 12 15 NO: We can see that for value 1 to be in the correct position it has to move from Array(7) to Array[0], therefore m > 3 (4) Write a complete C program to test your implementation of the C functions in Q1, Q2, and Q3. In addition, write/use c functions EnterArrayData(int size, int data[]) and PrintArrayData(int size, int data[]), to allow the user to enter the data for the array and display the array data when needed (40 Points]

Answer 1

below c code is complete implementation of all questions.

- x "C:\Users\Shivraj kumar\Desktop\che imperfectSorted.exe" solution for question number 4 Enter the size of array Enter the array шо 1 4 2 6 3 Enter the degree of array in m 3 testing question number 3 yes array is partially sorted with degree m testing question 1, question 2 array are printed in sorted order 1 2 3 4 6 searching by binary search enter the value want to search 5 is not present in array and it return -1 Process returned © (@xo) execution time : 24.583 S Press any key to continue. Activate Windows Go to Settings to activate Windows. O Type here to search P A UD 09:54 10) 19-02-2020 W

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

int search(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l) / 2;
if (arr[mid] == x)
{
return mid;
}
if (arr[mid] > x)
{
return search(arr, l, mid - 1, x);
}

else
{
return search(arr, mid + 1, r, x);
}

}
return -1;
}
void selectionSort(int arr[], int n)
{
int i, j, index;
for (i = 0; i < n-1; i++)
{

index = i;
for (j = i+1; j < n; j++)
{
if (arr[j] < arr[index])
{
index = j;
}

}
swap(&arr[index], &arr[i]);
}
}
int IsPartiallySorted(int high,int m ,int a[],int arr[],int low,int plow)
{
if(low<=high)
{
int index=search(arr,plow,high,a[low]);
if(abs(index-low)<=m)
{
return IsPartiallySorted(high,m,a,arr,low+1,plow);
}
else
{

return 0;
}
}
return 1;
}
int* EnterArrayData(int n)
{
int i;
int *a;
a=(int*)malloc(sizeof(int)*n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
return a;
}
void PrintArrayData(int *a,int n)
{
int i;
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
int main()
{
printf("solution for question number 4 \n");
int n,i,j;
printf("Enter the size of array\n");
scanf("%d",&n);
int *a,arr[n];
printf("Enter the array\n");
a=EnterArrayData(n); //takes input from array
printf("\n");
PrintArrayData(a,n);
for(i=0;i<n;i++)
{
arr[i]=a[i];
}
int m;
printf("Enter the degree of array in m\n");
scanf("%d",&m);

selectionSort(arr,n); //selection sort
printf(" testing question number 3\n");
int check =IsPartiallySorted(n-1,m,a,arr,0,0); //method to check partially sorted via recursion
if(check)
{
printf("yes array is partially sorted with degree m\n");
}
else
{

printf("no array is partially sorted with degree m\n");
}

printf(" testing question 1 , question 2\n");
printf("array are printed in sorted order\n");
PrintArrayData(arr,n);

printf("searching by binary search\n");
int p;
printf("enter the value want to search\n");
scanf("%d",&p);
int s=search(a,0,n-1,p);
if(s>=0)
{
printf("%d is present at index %d ",p,s);
}
else
{

printf("%d is not present in array and it return %d",p,s);
}

return 0;
}