Question

I. Write a computer program to do the following tasks: a) read a ist of integer data items into to an aray: b) date items that need to be sorted by using the bubble sort algorithm; c) using a binary scarch algorithm to determine the position of a specific item in the list. In the bubble sort procedure, you need to print the left and right endpoints for each searching step. Your program should print the location of the data item if the data item is found and print 0 if the item is not found. The data set for this project is as follows: 28, 3, 47, -51, 30, 44, 21, 4, 82, 98, 71, -34, 0, 17, 33, 21, 89, 7, 81, 68, 2, 8, 77, 12, 3, 7, 8, 53, 26, 47, 63, 79, -34, 80, 77, 32, 15 Run your program twice a) Find the location of the number 30 in the list. b) Find the location of the number 96 in the list.

Answer 1

Since you have not mentioned the language of your preference, I am providing the code in C.

CODE

// C program for implementation of Bubble sort

#include <stdio.h>

void swap(int *xp, int *yp)

{

  int temp = *xp;

  *xp = *yp;

  *yp = temp;

}

// A function to implement bubble sort

void bubbleSort(int arr[], int n)

{

int i, j;

for (i = 0; i < n-1; i++)

  // Last i elements are already in place

  for (j = 0; j < n-i-1; j++)

    if (arr[j] > arr[j+1])

      swap(&arr[j], &arr[j+1]);

}

// A recursive binary search function. It returns

// location of x in given array arr[l..r] is present,

// otherwise -1

int binarySearch(int arr[], int l, int r, int x)

{

printf("\nLeft endpoint: %d, right endpoint: %d\n", l, r);

if (r >= l) {

int mid = l + (r - l) / 2;

// If the element is present at the middle

// itself

if (arr[mid] == x)

return mid;

// If element is smaller than mid, then

// it can only be present in left subarray

if (arr[mid] > x)

return binarySearch(arr, l, mid - 1, x);

// Else the element can only be present

// in right subarray

return binarySearch(arr, mid + 1, r, x);

}

// We reach here when element is not

// present in array

return -1;

}

/* Function to print an array */

void printArray(int arr[], int size)

{

  int i;

  for (i=0; i < size; i++)

    printf("%d ", arr[i]);

  printf("\n");

}

// Driver program to test above functions

int main()

{

int n;

printf("enter the number of elements: ");

scanf("%d", &n);

  int arr[n];

for (int i=0;i<n; i++) {

printf("Enter element %d: ", i+1);

scanf("%d", &arr[i]);

}

  bubbleSort(arr, n);

  printf("Sorted array: \n");

  printArray(arr, n);

int pos;

pos = binarySearch(arr, 0, n-1, 30);

if (pos == -1) {

printf("\n0");

} else {

printf("\n%d", pos);

}

pos = binarySearch(arr, 0, n-1, 96);

if (pos == -1) {

printf("\n0");

} else {

printf("\n%d", pos);

}

  return 0;

}