Problem Statement Write a C++ program to implement a few sorting and searching a

Question

Problem Statement Write a C++ program to implement a few sorting and searching algorithms. The program should display the following menu repeatedly to allow user to read a sequence of integers, print the content of the sequence, sorting the sequence in non-descending order using one of three sorting algorithms and di play a trace of execution for each one, search for a key in the sequence using one of two algorithms, or exit from the program. 1. Read 2. Print 3. Sort 4. Shuffle 5. Search 6. Quit Option 3 should use the following submenu: 1. Selection sort 2. Insertion sort 3. Bubble sort 4. Quit Option 5 should use the following submenu: 1. Sequential search 2. Binary search 3. Quit For each of the three sorting functions, you should trace the sorting procedure for each algorithm, display the sequence of the data after each iteration. You can use the sample output shown below for reference Each of the two scarching functions should count the number of data comparisons made to perform the operation and print the count. Note after the user chooses the binary search, the data items in the sequence will be put in the non-descending order (use one of three sorting algorithms you implemented for Option 3) first, before applying binary search algorithm to find the target.

Explanation / Answer

The code as you want, I've made some assumption and changes to make it more useful !

code:

# include <iostream>
using namespace std;

int INITIAL_CAPACITY=5;
class IntSeq{
   int capacity,count;
   int *seq;
  
   public:
       IntSeq(){
       capacity=INITIAL_CAPACITY;
       seq=new int[INITIAL_CAPACITY];
       }
      
       ~IntSeq(){
       }
      
       IntSeq(int    in_capacity){
           capacity=in_capacity;
           seq=new int[in_capacity];
       }
      
       void insert(int item){
                if(count==(capacity)) cout<<"max capacity reached. Cannot enter more numbers";
                else seq[count++]=item;
       }
      
       void print(){
           cout<<count<<" Sequence ";
           for(int i=0;i<count;i++) cout<<seq[i]<<" ";
           cout<<" ";
       }
      
      
       int sequential_search(int key)
       {
       int compare_count=0;
       int i=0;
       for(;i<count;i++)
       {
          if(key==seq[i]) { compare_count++; break;}
          compare_count++;
       }
       if(i==count) return -1;
       else return i;
       }
      
       int binary_search(int key)
       {
       bubble_sort();
       int l=0,h=count;
       int mid=(l+h)/2;
      
       while(l<=h && seq[mid]!=key)
       {
          mid=(l+h)/2;
          cout<<"mid "<<mid;
       }
       if(seq[mid]==key) return mid;
       else return -1;
       }
      
       void shuffle()
       {
       int temp[count];
       for(int i=1;i<count;i=i+2) {int t=seq[i]; seq[i]=seq[i-1]; seq[i-1]=t;}
       }
      
       void bubble_sort()
       {
       cout<<" ";
       for(int i=0;i<count;i++)
       {
          cout<<" Iteration "<<i+1<<"   ";
          for(int j=i+1;j<count;j++)
           {
              if(seq[i]>seq[j]){int t=seq[i]; seq[i]=seq[j]; seq[j]=t;}
           }
           for(int k=0;k<count;k++)cout<<seq[k]<<" ";
       }
        }
  
  
      
       void selection_sort()
       {
       cout<<" ";
       for(int i=0;i<count;i++)
       {
          cout<<" Iteration "<<i+1<<"   ";
          int min=i,j;
          for(j=i+1;j<count;j++)
           {
              if(seq[min]>seq[j]) min=j;
           }
         
           int t=seq[min]; seq[min]=seq[i]; seq[i]=t;
         
           for(int k=0;k<count;k++)cout<<seq[k]<<" ";
       }
       }
      
      
  
       void insertion_sort()
       {
       cout<<" ";
         for (int i = 1; i < count; i++)
         {
            int ci=seq[i];
            for (int j = i; j >= 1; j--)
           {
               if (seq[j] < seq[j-1])
               {
               int temp = seq[j];
                seq[j] = seq[j-1];
                seq[j-1] = temp; }
           else break;
          
           cout<<" Insert "<<ci<<"    ";
           for(int k=0;k<count;k++)cout<<seq[k]<<" ";
        }
       }
       }
};

IntSeq obj;
int main()
{
void read();
void printm();
void sort();
void search();
void shuffle();

int capacity;
cout<<"Enter max capacity of array ";
cin>>capacity;
cout<<" initializing array ";
obj=IntSeq(capacity);
cout<<"initialization complete Array created with max capacity "<<capacity<<" ";

int choice=0;
while(choice!=6)
{
cout<<"1.read 2.print 3.sort 4.shuffle 5.search 6.quit Enter your choice no. : ";
cin>>choice;
switch(choice)
{
   case 1: read(); break;
   case 2: printm(); break;
   case 3: sort(); break;
   case 4: shuffle(); break;
   case 5: search(); break;
   case 6: break;
   default: cout<<" you entered wrong choice"; continue;
}
}

}

void read(){
int item=0,no;
cout<<"Enter no. of elements you want to add: "; cin>>no;
for(int i=1;i<=no;i++)
{
   cout<<"Enter next element: ";
   cin>>item;
   obj.insert(item);
}
cout<<" ";
}

void shuffle()
{
obj.shuffle();
}
void printm()
{
obj.print();
}

void search()
{
int key;
cout<<"Enter key to serach "; cin>>key;
cout<<"Enter your choice 1.Sequential search 2.Binary search ";
int choice;
cin>>choice;
int res=-1;
while(true)
{
if(choice==1) {res=obj.sequential_search(key); break;}
else if(choice==2) {res=obj.binary_search(key); break;}
else cout<<" You entered wrong choice Re-enter: "; continue;
}


if(res==-1) cout<<"Key doesnot found";
else        cout<<"Key found at index "<<res<<" (position "<<res+1<<") ";
cout<<" ";
}


void sort()
{
cout<<"Enter your choice 1.Bubble sort 2.Insertion sort 3.Selection sort ";
int choice;
cin>>choice;
while(true)
{
if(choice==1) {obj.bubble_sort(); break;}
else if(choice==2) {obj.insertion_sort(); break;}
else if(choice==3) {obj.selection_sort(); break;}
else cout<<" You entered wrong choice Re-enter: "; continue;
cout<<" ";
}
obj.print();
cout<<" ";
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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