Question

You can use any programming languages

Using a random generator, compute 1000 integers between 1 and 1000. There will be duplicates in the array. Sort the array using bubble sort and merge sort. The two sorted arrays should agree. Then pick at random one element from your sorted array and use a binary search to find its position in the array.

Answer 1

C program :-

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

int b_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 b_search(arr, l, mid - 1, x);

return b_search(arr, mid + 1, r, x);
}
  
return -1;
}

void merge_func(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
  
int L[n1], R[n2];
  
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
  
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
  
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
  
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
  
void m_sort(int arr[], int l, int r)
{
if (l < r)
{
int m = l+(r-l)/2;
  
m_sort(arr, l, m);
m_sort(arr, m+1, r);
  
merge_func(arr, l, m, r);
}
}

int main(void)
{
int arr[1000];
int b_arr[1000];
int m_arr[1000];
int temp;
int ele_ind;
int ele;
  
for(int i = 0; i<1000; i++) {
arr[i] = (rand() % 1000) + 1;
b_arr[i] = arr[i];
m_arr[i] = arr[i];
}

/* binary search */   
for (int i = 0 ; i < 1000 - 1; i++)
{
for (int j = 0 ; j < 1000 - i - 1; j++)
{
if (b_arr[j] > b_arr[j+1])
{
temp = b_arr[j];
b_arr[j] = b_arr[j+1];
b_arr[j+1] = temp;
}
}
}
  
m_sort(m_arr, 0, 1000 - 1);
  
ele_ind = (rand() % 1000) + 1;
ele = arr[ele_ind];
  
printf("The index of the element %d in sorted array is %d",ele,b_search(b_arr, 0, 999, ele));

return 0;
}