c++ programming 2.3 Sorting Implement a base class called Sort. All other sortin
ID: 3839247 • Letter: C
Question
c++ programming
2.3 Sorting Implement a base class called Sort. All other sorting algorithms must be derived from this class. You should decide how you are going to store the data that is going to be sorted or worked with as part of your sorting process. It is up to you to decide the storage mechanism. Step 1: Implement bubble sort in a class called Bubblesort that extends Sort. http://en.wikipedia.org/wiki/Bubble-sort Step 2: Implement quick sort in a class called QuickSort that extends Sort. http://en.wikipedia.org/wiki/Quicksort As a requirement, for the pivot selection, when the list is of length at least 3, please always chose the third value in the list (e.g., if the (sub)list is formed by 4 elements 2, 4, 9, 1, then the pivot is 9)Explanation / Answer
------Sort and Search in c++---------
#include <iostream>
using namespace std;
#define MAX 50
class Sort{
public:
int arr[MAX], n,flag = 0;
void getdata()
{
cout<<"Enter the elements ";
for(int i=0;i<n;i++)
cin>>arr[i];
}
void showdata()
{
cout<<" --Output-- ";
if(flag == 0)
cout<<"false";
else
cout<<"true";
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
}
};
class BubbleSort: public Sort{
void sortlogic()
{
int temp;
for(int i=0;i<n;i++){
for(int j=0,change=0;j<n;j++){
if(arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
change++;
cout<<" arr[j] = "<<arr[j]<<" arr[j+1] = "<<arr[j+1];
}
}
cout<<endl;
if(change==0)
break;
}
}
};
class QuickSort: public Sort{
void sortlogic(int x[], int lb, int ub)
{
int j;
if(lb >= ub)
return;
showdata();
pivot(x,lb,ub,j);
sortit(x,lb,j-1);
sortit(x,j+1,ub);
}
void pivot(int x[],int lb,int ub,int &pj)
{
int a, down, temp, up;
a = x[lb];
up = ub;
down = lb;
while(down < up)
{
while(x[down] <= a)
down++;
while(x[up] > a)
up--;
if(down < up)
{
temp = x[down];
x[down] = x[up];
x[up] = temp;
}
}
x[lb] = x[up];
x[up] = a;
pj = up;
}
};
class RecursiveBinarySearch
{
public:
int recursivebsearch(int arr[], int num, int beg, int end)
{
int mid;
if (beg > end){
cout << "Number is not found";
return 0;
}
else
{
mid = (beg + end) / 2;
if(arr[mid] == num){
cout<<"Number is found at "<<mid<<" index ";
return 1;
}
else if(num > arr[mid])
{
recursivebsearch(arr, num, mid+1, end);
} else if (num < arr[mid]) {
recursivebsearch(arr, num, beg , mid-1);
}
}
}
};
void main()
{
BubbleSort bs;
QuickSort qs;
RecursiveBinarySearch rbs;
qs.getdata();
qs.sortlogic();
flag = rbs.recursivebsearch()
qs.showdata();
getch();
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.