C++ data strucs algorithms. follow instructions for each part please. thank you!

Question

C++ data strucs algorithms. follow instructions for each part please. thank you!

Required Classes and Methods NOT functions.

To receive full credit, programmers must apply coding conventions for code block indentation, comments describing methods/classes, white space between code blocks, and variable/method/class naming conventions.

Implement Inheritance, Getters, Setters, and other OOP tools as needed.

A.

Create and implement a Bubble Sort Algorithm method that can be called to sort the given arrays.

B.

Create and implement a Insertion Sort Algorithm method that can be called to sort the given arrays.

Explanation / Answer

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order.[Ref : Wikipedia]

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.[Ref : Wikipedia]

Please find the C++ program below:

#include<iostream>
using namespace std;

class Sorting
{  
   int count;
   public:
   void bubbleSort(int *, int);
   void insertionSort(int *, int);
};

void Sorting::bubbleSort(int *ar, int n){
   int tmp,i,j;
   for(i = 0; i<n-1; i++)
   {   //To keep track of swaps; if no swap performed in a pass, it will break
       count =0;
       for(j=0; j<n-1-i; j++){
           if(ar[j] > ar[j+1]){
               // Swapping logic
               tmp = ar[j];
               ar[j] = ar[j+1];
               ar[j+1] = tmp;
               count++;
           }
       }
       if(count == 0)
           break;
   }
}

void Sorting::insertionSort(int *ar, int n){
   int tmp, i, j;
   for(i=1; i<n; i++){
       tmp= ar[i];
       for(j = i-1; j>=0 && tmp<ar[j]; j--)
       {   // Moving all the large elements to higher places to accomodate the smaller element
           ar[j+1] = ar[j];
       }
       ar[j+1] = tmp;
   }  
}

int main()
{
   int n,i, ans;
   int ar[10]={3,5,1,6,4,8,12,45,9,2};
   Sorting s;
   cout<<"Enter 1 for BubbleSort, 2 for Insertion Sort";
   cin>>ans;
   if(ans == 1)
       s.bubbleSort(ar, 10);
   else if(ans == 2)
       s.insertionSort(ar, 10);
   else
   {
       cout<<"Invalid Choice";
   }  
   for(i=0; i< 10; i++)
   {
       cout<<ar[i]<<" ";
   }
   cout<<" ";
   return 0;
}

Note: To compile the program, use following command in linux:

g++ Sorting.cpp -o Sorting

And to run:

./Sorting

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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