c++programming 2.3 Sorting Implement a base class called Sort. All other sorting

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

The bellow program satisfies the above requirement as follows:-
----------------------------------------------------------------------------------------------------

#include <iostream>

using namespace std;

void Q_sort(int[],int,int);
int Partition_QSort(int[],int,int);

int main()
{
int a[50],n,i;
cout<<"Enter the number of inputs which you want to enter: ";
cin>>n;
cout<<" Enter Sample Input: ";
  
for(i=0;i<n;i++)
cin>>a[i];
  
Q_sort(a,0,n-1);                               //Q_sort method uses quick sort code
cout<<" Sample output: ";
cout<<B_Search(a,1,0,n-1)<<" "                               //for searching 1 in the given array
for(i=0;i<n;i++)
cout<<a[i]<<" ";
  
return 0;
}

Boolean B_Search(int a[],int n, int low,int High)
{
   int mid;
   if(low>High)
   {
       return false;
   }
   else{
       mid=(low+High)/2;
       if(a[mid]==n)
       {
           return true;
       }
       else if(n>a[mid]){
           B_Search(a,n,mid+1,High);
       }
       else if(n<a[mid]){
           B_Search(a,n,low,mid-1);
       }
   }
}

void Q_sort(int a[],int low,int High)
{
int j;
if(low<High)
{
j=Partition_QSort(a,low,High);
Q_sort(a,low,j-1);
Q_sort(a,j+1,High);
}
}

int Partition_QSort(int a[],int low,int High)
{
int v,i,j,temp;
v=a[low];
i=low;
j=High+1;
  
do
{
do
i++;
  
while(a[i]<v&&i<=High);
  
do
j--;
while(v<a[j]);
  
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}while(i<j);
  
a[low]=a[j];
a[j]=v;
  
return(j);
}

Output:-
------------
Enter the number of inputs which you want to enter:
8
Enter Sample Input:
1 3 5 4 -5 100 777 2014
Sample output:
true -5 1 3 4 5 100 2014 777

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.