write a C++ program (in classes) that takes the numbers 38, 5, 2, 70, 39, 14, 27
ID: 3681718 • Letter: W
Question
write a C++ program (in classes) that takes the numbers 38, 5, 2, 70, 39, 14, 27, 3, and 100 and does the following: asks the user to select the preferred data structure (array or linked list) asks the user to select the preferred algorithm (search or sort) asks the user to select the preferred search or sorting algorithm, depending on the previous selection sorting algorithms: selection sort, bubble sort, merge sort, quicksort, insertion sort searching algorithms: selection search (linear search), binary search carries out the user-selected searching or sorting algorithm and asks the user if they would like to continue - the program continues executing until the user indicates that they wish to exit the program
Explanation / Answer
#include <iostream>
using namespace std;
class arrayStructure{
public:
void swap(int *xp, int *yp){
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void selectionSort(int arr[]){
int i, j, min_idx,n=9;
// One by one move boundary of unsorted subarray
for(i=0;i<n-1;i++){
// Find the minimum element in unsorted array
min_idx = i;
for(j=i+1;j< n;j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element with the first element
swap(&arr[min_idx], &arr[i]);
}
}
void bubbleSort(int arr[]){
int i, j, n=9;
for (i=0;i<n-1;i++){
// Last i elements are already in place
for (j=0;j<n-i-1;j++){
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}
}
}
void mergeSort(int arr[], int l, int r){
if (l < r)
{
int m = l+(r-l)/2; //Same as (l+r)/2 but avoids overflow for large l & h
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */
void merge(int arr[], int l, int m, int r){
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[n1], R[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
int partition (int arr[], int l, int h){
int x = arr[h];
int i = (l - 1);
for (int j = l; j <= h- 1; j++)
{
if (arr[j] <= x)
{
i++;
swap (&arr[i], &arr[j]);
}
}
swap (&arr[i + 1], &arr[h]);
return (i + 1);
}
/* A[] --> Array to be sorted,
l --> Starting index,
h --> Ending index */
void quickSort(int arr[], int l, int h){
if (l < h)
{
/* Partitioning index */
int p = partition(arr, l, h);
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, h);
}
}
void insertionSort(int arr[]){
int i, key, j, n=9;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}
void printArray(){
int i;
for(i=0;i<9;++i)
cout<<arr[i]<<" ";
cout<<endl;
}
int linearSearch(int arr[], int x){
int i, n=9;
for (i=0; i<n; i++)
if (arr[i] == x)
return i;
return -1;
}
int binarySearch(int arr[], int l, int r, int x){
if (r >= l)
{
int mid = l + (r - l)/2;
// If the element is present at the middle itself
if (arr[mid] == x) return mid;
// If element is smaller than mid, then it can only be present
// in left subarray
if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
// Else the element can only be present in right subarray
return binarySearch(arr, mid+1, r, x);
}
// We reach here when element is not present in array
return -1;
}
int arr[9]={38,5,2,70,39,14,27,3,100};
};
int main(){
while(true){
cout<<"Which data sructure you want to select:-"<<endl;
cout<<" 1-for array"<<endl;
cout<<" 2-for linked list"<<endl;
cout<<" 3-for Quit"<<endl;
int select;
cin>>select;
if(select==1){
arrayStructure obj;
cout<<"What you want do search or sort"<<endl;
cout<<" 1-for Sort"<<endl;
cout<<" 2-for Search"<<endl;
int temp;
cin>>temp;
if(temp==1){
cout<<"Which algorithm you want to prefer"<<endl;
cout<<" 1-for Selection sort"<<endl;
cout<<" 2-for bubble sort"<<endl;
cout<<" 3-for merge sort"<<endl;
cout<<" 4-for quick sort"<<endl;
cout<<" 5-for insertion sort"<<endl;
int enter;
cin>>enter;
if(enter==1){
obj.selectionSort(obj.arr);
obj.printArray();
}
else if(enter==2){
obj.bubbleSort(obj.arr);
obj.printArray();
}
else if(enter==3){
obj.mergeSort(obj.arr,0,8);
obj.printArray();
}
else if(enter==4){
obj.quickSort(obj.arr,0,8);
obj.printArray();
}
else if(enter==5){
obj.insertionSort(obj.arr);
obj.printArray();
}
}
else if(temp==2){
cout<<"Which algorithm you want to prefer"<<endl;
cout<<" 1-for Linear search"<<endl;
cout<<" 2-for Binary search"<<endl;
int enter;
cin>>enter;
if(enter==1){
int ind=obj.linearSearch(obj.arr, 3);
cout<<"Element is found at index "<<ind<<endl;
}
else if(enter==2){
int ind=obj.binarySearch(obj.arr,0,8,27);
cout<<"Element is found at index "<<ind<<endl;
}
}
}
else if(select==2){
//linked list
}
else if(select==3){
break;
}
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.