that sorts a list of natural numbers using the bubble sort algorithm described i
ID: 3591773 • Letter: T
Question
that sorts a list of natural numbers using the bubble sort algorithm described in project 4, page 557, chapter 9, sixth edition (or project 4, page 483, chapter 9, fifth edition); 1. 2. and then looks for a particular number using the binary search algorithm defined in project 12, page 560, chapter 9, sixth edition (or project 12, page 486, chap- ter 9, fifth edition). Sample run follows: 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 2 Do you want to continue CY/N]: Y Enter the number to search: 5 Number 5 does not exist! Do you want to continue [Y/N] N Good bye!Explanation / Answer
#include<iostream>
#define MAX 100
using namespace std;
//Base class Number definition
class Number
{
//Data member to store number of elements to store in array
int len;
protected:
//Access specified protected to make this available to derived class
//To store the numbers
int numbers[MAX];
public:
//Prototype of member functions
Number();
void getNumbers();
void setNumbers();
int getLength();
void setLength(int);
};//End of class
//Default constructor to initialize data members
Number::Number()
{
len = 0;
for(int x = 0; x < MAX; x++)
numbers[x] = 0;
}//End of function
void Number::setLength(int no)
{
len = no;
}
//Function to return the length of array because no is private
int Number::getLength()
{
return len;
}//End of function
//Function to display numbers to the array
void Number::getNumbers()
{
//Loops till length of the array and displays the numbers
for(int x = 0; x < len; x++)
cout<<numbers[x]<<" ";
}//End of function
//Function to display numbers
void Number::setNumbers()
{
//Loops till length of the array and accepts the numbers from the user
for(int x = 0; x < len; x++)
cin>>numbers[x];
}//End of function
//Derived class Sort derived from base class Number
class Sort : public Number
{
//Data member to store number of elements required by the user for array
int n;
public:
//Prototype of member functions
Sort();
void getData();
void bubbleSort();
};//End of class
//Default constructor to initialize data members
Sort::Sort()
{
n = 0;
}//End of constructor
//Function to accept length of the array and numbers for array
void Sort::getData()
{
cout<<" Enter the number of naturals: ";
cin>>n;
//Sets the length of the array by calling base class member function
setLength(n);
cout<<" Enter the natural numbers to sort: ";
setNumbers();
//Accepts numbers for array by calling the function
}//End of function
//Function to sort the elements or the array in ascending order using bubble sort
void Sort::bubbleSort()
{
//Accepts data
getData();
int temp, x, y;
//Loops till length of the array
for(x = 0; x < getLength(); x++)
{
//Loops till length of the array minus x minus one times
for(y = 0; y < getLength() - x - 1; y++)
{
//Checks if current index position of the array is greater than the next index position of the array
if(numbers[y] > numbers[y + 1])
{
//Swapping process
temp = numbers[y];
numbers[y] = numbers[y + 1];
numbers[y + 1] = temp;
}//End of if condition
}//End of inner for loop
}//End of outer for loop
cout<<" Numbers sorted in ascending order: ";
//Displays the data using base class member function
getNumbers();
}//End of function
//Derived class Search derived from base class Sort
class Search : public Sort
{
//Data member to store number to search
int num;
public:
//Prototype of member functions
Search();
void getData();
void binarySearch();
};//End of class
//Default constructor to initialize data members
Search::Search()
{
num = 0;
}//End of constructor
//Function to accept number to search
void Search::getData()
{
cout<<" Enter the number to search: ";
cin>>num;
}//End of function
//Function to search a number from the array using binary search
void Search::binarySearch()
{
//Accepts the number to search
getData();
//Local variable to store starting , end and middle index position of the array
int Beg, End, Mid;
//Local variable to check number found or not
int flag;
//Initializes the variables to zero
Beg = flag = 0;
//Set the end to length of the array minus one because the starting index position of the array is zero
End = getLength() - 1;
//Loops till begin is less than or equals to end position
while(Beg <= End)
{
//Calculates the mid index position
Mid = (Beg + End) / 2;
//Checks if the search number is equal to array mid index position value
if(num == numbers[Mid])
{
//Display the number and index position where found
cout<<" Number "<<num<<" is found at position "<<Mid + 1;
//Set the flag value to one for found
flag = 1;
//Come out of the loop
break;
}//End of if condition
//Checks if the search number is less than the array mid index position value
else if(num < numbers[Mid])
//Set the end to mid minus one because mid index position is already considered above
//Array is sorted in ascending order so number is available in the second half part of the array
End = Mid - 1;
//Otherwise the search number is greater than the array mid index position value
else
//Set the beginning to mid plus one because mid index position is already considered above
//Array is sorted in ascending order so number is available in the first half part of the array
Beg = Mid + 1;
}//End of while loop
//Checks if the flag value is zero then number not found
if(flag == 0)
cout<<" Number "<<num<<" does not exist!";
}//End of function
//Main function definition
int main()
{
//Creates an object of the class Search
Search se;
char choice;
//Calls the function for bubble sort
se.bubbleSort();
do
{
//Calls the function for bi8nary search
se.binarySearch();
//Accepts user choice to continue or not
cout<<" Do you want to continue [Y /N ]: ";
cin>>choice;
//Checks if user choice is 'N' or 'n' the stop
if(choice == 'N' || choice == 'n')
break;
}while(1); //End of do - while loop
}//End of main function
Sample Run:
Enter the number of naturals: 5
Enter the natural numbers to sort: 10
2
56
22
48
Numbers sorted in ascending order: 2 10 22 48 56
Enter the number to search: 2
Number 2 is found at position 1
Do you want to continue [Y /N ]: y
Enter the number to search: 22
Number 22 is found at position 3
Do you want to continue [Y /N ]: y
Enter the number to search: 50
Number 50 does not exist!
Do you want to continue [Y /N ]: n
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.