Homework SourseBinary Search Bubble Sort Using functions write a C program
Binary Search & Bubble Sort
Using functions, write a C++ program:
1- that sorts a list of natural numbers using the bubble sort algorithm (The bubble sort is an other technique for sorting an array.A bubble sort compares adjacent array elements and exchanges their values if they’re out of order. In this way, the smaller values “bubble” to the top of the array (toward element 0), while the larger values sink to the bottom of the array. After the first pass of a bubble sort, the last array element is in the correct position; after the second pass, the last two elements are correct, and so on. Thus, after each pass, the unsorted portion of the array contains one less element. Write and test a function that imple- ments this sorting method. )
Sample run follows:
The binary search algorithm that follows may be used to search an array when the elements are sorted. This algorithm is analogous to the following approach for finding a name in a telephone book a. Open the book in the middle, and look at the middle name on the page. b. If the middle name isn\'t the one you\'re looking for, decide whether it comes before or after the name you want. Take the appropriate half of the section of the book you were looking in and repeat these steps until you land on the name. ALGORITHM FOR BINARY SEARCH 1. Let bottom be the subscript of the initial array element. 2. Let top be the subscript of the last array element 3. Let found be false. 4. Repeat as long as bottom isn\'t greater than top and the target has not been found. 5. Let middle be the subscript of the element halfway between bottom and top 6. If the element at middle is the target 7. Set found to true and index to middle. Else if the element at middle is larger than the target 8. Let top be middle 1. Else 9. Let bottom be middle 1. Write and test a function binarysearch that implements this algorithm for an array of integers. When there is a large number of array elements, which function do you think is faster binary Search or the linear search function of Listing?Solution
#include <iostream>
using namespace std;
void bubbleSort(int a[], int size){
int temp = 0;
for(int i=0; i < size; i++){
for(int j=1; j < (size-i); j++){
if(a[j-1] > a[j]){
//swap the elements!
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
}
int binarySearch(int a[], int size, int key, int first, int last){
int middle = (first+last)/2;
while (first <= last)
{
if(a[middle] < key)
{
first = middle + 1;
}
else if(a[middle] == key)
{
return middle+1;
break;
}
else
{
last = middle - 1;
}
middle = (first + last)/2;
}
if(first > last)
{
return -1;
}
}
int main()
{
int *pvalue = NULL;
int n;
pvalue = new int;
cout << \"Enter the number of naturals: \";
cin >> *pvalue;
const int size = *pvalue;
int *nums = 0;
nums = new int[size];
cout<<\"Enter the natural numbers to sort: \";
for(int i=0; i<size; i++){
cin >>nums[i];
}
bubbleSort(nums, size);
cout<<\"Numbers sorted in ascending order: \"<<endl;
for(int i=0; i<size; i++){
cout<<nums[i]<<\" \";
}
cout<<endl;
char ch;
while(true){
cout<<\"Enter the number to search: \";
cin >> n;
int result = binarySearch(nums, size, n, 0, size-1);
if( result != -1){
cout<<\"Number \"<<n<<\" is found at position: \"<<result<<endl;
}
else{
cout<<\"Number \"<<n<<\" does not exist!\"<<endl;
}
cout<<\"Do you want to continue [Y/N]: \";
cin >> ch;
if(ch == \'n\'||ch==\'N\'){
cout<<\"Good bye!\"<<endl;
break;
}
}
return 0;
}
OUtput:
sh-4.2$ g++ -o main *.cpp
sh-4.2$ main
Enter the number of naturals: 10
Enter the natural numbers to sort: 12 34 4 0 22 3 6 18 1 11
Numbers sorted in ascending order:
0 1 3 4 6 11 12 18 22 34
Enter the number to search: 3
Number 3 is found at position: 3
Do you want to continue [Y/N]: y
Enter the number to search: 5
Number 5 does not exist!
Do you want to continue [Y/N]: n
Good bye!
