Implement merge sort and merge
#include <iostream>
using namespace std;
void * merge(int arr[], int start1, int end1, int start2, int
end2){
int * combined = new int[end2-start1 + 1];
}
void mergeSort(int arr[], int start, int end){
//base case: down to 1 item, do nothing
//recursive case:
//MergeSort(left)
//MergeSort(right)
//Merge(left, right)
int m = (end - start) / 2;
if(start==end){ }
else {
mergeSort(arr, start, m);
mergeSort(arr, m+1, end);
merge(arr, start, m, m+1, end);
}
}
void fill(int arr[], int count){
for(int i = 0; i < count; i++){
cout << "Enter number: ";
cin >> arr[i];
}
}
void display(int arr[], int count){
for(int i = 0; i < count; i++){
cout << arr[i] << endl;
}
}
int main() {
cout << "How many items: ";
int count;
cin >> count;
int * arr = new int[count];
fill(arr, count);
mergeSort(arr, 0, count-1);
display(arr, count);
}
Program
#include <iostream>
using namespace std;
void * merge(int arr[], int start1, int end1, int start2, int
end2){
int * combined = new int[end2-start1 + 1];
int i, j, p;
i = start1;
p = 0;
j = start2;
// merge two parts into combined
while (i <= end1 && j <= end2)
{
if (arr[i] < arr[j])
{
combined[p] =
arr[i];
p++;
i++;
}
else
{
combined[p] =
arr[j];
p++;
j++;
}
}
// insert all the elements from i to end1 into
combined
while (i <= end1)
{
combined[p] = arr[i];
p++;
i++;
}
// insert all the elements from j to end2 into
combined
while (j <= end2)
{
combined[p] = arr[j];
p++;
j++;
}
// assigning values from combined[] to arr[]
for (i = start1; i <= end2; i++)
{
arr[i] = combined[i-start1];
}
}
void mergeSort(int arr[], int start, int end){
//base case: down to 1 item, do nothing
//recursive case:
//MergeSort(left)
//MergeSort(right)
//Merge(left, right)
int m = (end + start) / 2;
if(start<end){
mergeSort(arr, start, m);
mergeSort(arr, m+1, end);
merge(arr, start, m, m+1, end);
}
}
void fill(int arr[], int count){
for(int i = 0; i < count; i++){
cout << "Enter number: ";
cin >> arr[i];
}
}
void display(int arr[], int count){
for(int i = 0; i < count; i++){
cout << arr[i] << endl;
}
}
int main() {
cout << "How many items: ";
int count;
cin >> count;
int * arr = new int[count];
fill(arr, count);
mergeSort(arr, 0, count-1);
display(arr, count);
}
Output
// Merge sort in C #include <stdio.h> // Merge two subarrays L and M into arr void merge(int arr[], int p, int q, int r) { // Create L ← A[p..q] and M ← A[q+1..r] int n1 = q - p + 1; int n2 = r - q; int L[n1], M[n2]; for (int i = 0; i < n1; i++) L[i] = arr[p + i]; for (int j = 0; j < n2; j++) M[j] = arr[q + 1 + j]; // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A[p..r] while (i < n1 && j < n2) { if (L[i] <= M[j]) { arr[k] = L[i]; i++; } else { arr[k] = M[j]; j++; } k++; } // When we run out of elements in either L or M, // pick up the remaining elements and put in A[p..r] while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = M[j]; j++; k++; } } // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr[], int l, int r) { if (l < r) { // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); } } // Print the array void printArray(int arr[], int size) { for (int i = 0; i < size; i++) printf("%d ", arr[i]); printf("\n"); } // Driver program int main() { int arr[] = {6, 5, 12, 10, 9, 1}; int size = sizeof(arr) / sizeof(arr[0]); mergeSort(arr, 0, size - 1); printf("Sorted array: \n"); printArray(arr, size); }
Implement merge sort and merge #include <iostream> using namespace std; void * merge(int arr[], int start1, int end1, int start2, int end2){ int * combined = new int[end2-start1 + 1]; ...
#include <iostream> using namespace std; bool binarySearch(int arr[], int start, int end, int target){ //your code here } void fill(int arr[], int count){ for(int i = 0; i < count; i++){ cout << "Enter number: "; cin >> arr[i]; } } void display(int arr[], int count){ for(int i = 0; i < count; i++){ cout << arr[i] << endl; } } int main() { cout << "How many items: "; int count; cin >> count; int * arr = new...
Merge Sort: Time Complexity: O(n log(n)) #include "stdafx.h" #include <iostream> #include <time.h> #include <stdlib.h> using namespace std; void combine(int *a, int low, int high, int mid) { int i, j, k, c[100000]; i = low; k = low; j = mid + 1; while (i <= mid && j <= high) { if (a[i] < a[j]) { c[k] = a[i]; k++; i++; } else { ...
must provide the following public interface: public static void insertSort(int [] arr); public static void selectSort(int [] arr); public static void quickSort(int [] arr); public static void mergeSort(int [] arr); The quick sort and merge sort must be implemented by using recursive thinking. So the students may provide the following private static methods: //merge method //merge two sorted portions of given array arr, namely, from start to middle //and from middle + 1 to end into one sorted portion, namely,...
#include <iostream> using namespace std; struct node { int base; int power; }; void insert(node ptr[],int basee,int powerr) { ptr[powerr].power=powerr; ptr[powerr].base=basee; } void addition(node ptr1[],int size1,node ptr2[],int size2,node ptr3[],int size3) { for(int j=0;j<=size1;j++) { ptr3[j].base=ptr3[j].base+ptr1[j].base; } for(int j=0;j<=size2;j++) { ptr3[j].base=ptr3[j].base+ptr2[j].base; } } void display(node ptr[],int size) { if(ptr[0].base!=0) cout<<ptr[0].base<<"+"; for(int i=1; i<=size; i++) { if(ptr[i].base!=0) cout<<ptr[i].base<<"x^"<<ptr[i].power<<"+"; } } int main() { bool choice1=true; bool choice2=true; int size1,size2,base1,base2,power1,power2; cout<<"enter the max power in polynominal 1"; cin>>size1; node *a= new node[size1+1]; for(int...
#include <iostream> using namespace std; struct node { int base=0; int power=0; }; void insert(node ptr[],int basee,int powerr) { ptr[powerr].power=powerr; ptr[powerr].base=basee; } void subtract(node ptr1[],int size1,node ptr2[],int size2,node ptr3[]) { for(int j=0;j<=size1;j++) { if(ptr1[j].base!=0) { ptr3[j].base=(ptr3[j].base)+(ptr1[j].base); ptr3[j].power=ptr2[j].power; } } for(int j=0;j<=size2;j++) { if(ptr2[j].base!=0) { ptr3[j].base=(ptr3[j].base)-(ptr2[j].base); ptr3[j].power=ptr2[j].power; } } } void addition(node ptr1[],int size1,node ptr2[],int size2,node ptr3[]) { for(int j=0;j<=size1;j++) { if(ptr1[j].base!=0) { ptr3[j].base=(ptr3[j].base)+(ptr1[j].base); ptr3[j].power=ptr2[j].power; } } for(int j=0;j<=size2;j++) { if(ptr2[j].base!=0) { ptr3[j].base=(ptr3[j].base)+(ptr2[j].base); ptr3[j].power=ptr2[j].power; } } } void display(node ptr[],int size)...
I need help with this code: #include <iostream> #include <cstdlib> #include <string> using namespace std; void dump(int ar[], int size) { cout << "\nDUMP [ "; for (int i=0; i<=size; i++) { cout << ar[i] << " "; } cout << "]\n\n"; } void quicksort(int ar[], int start, int end) { cout << "TOP OF SORT ===========================" << endl; dump(ar, start, end); int pivot = ar[end]; int left = start; int right = end - 1; int tmp; cout <<...
#include <iostream> #include <queue> using namespace std; class Graph { public: Graph(int n); ~Graph(); void addEdge(int src, int tar); void BFTraversal(); void DFTraversal(); void printVertices(); void printEdges(); private: int vertexCount; int edgeCount; bool** adjMat; void BFS(int n, bool marked[]); void DFS(int n, bool marked[]); }; Graph::Graph(int n=0) { vertexCount = n; edgeCount = 0; if(n == 0) adjMat = 0; else { adjMat = new bool* [n]; for(int i=0; i < n; i++) adjMat[i] = new bool [n]; for(int i=0;...
#include <iostream> using namespace std; int main(void) { int SIZE; cout<<"Enter the size of the array"<<endl; cin>>SIZE; int *numlist = new int[SIZE]; // Read SIZE integers from the keyboard for (int i = 0; i<SIZE; i++ ) { cout << "Enter value #" << i+1 << ": "; cin >> numlist[i]; } // Display the numbers in a reverse order for (int i = SIZE; i > 0; i--...
#include "stdafx.h" #include <iostream> using namespace std; class dateType { private: int dmonth; int dday; int dyear; public: void setdate (int month, int day, int year); int getday()const; int getmonth()const; int getyear()const; int printdate()const; bool isleapyear(int year); dateType (int month=0, int day=0, int year=0); }; void dateType::setdate(int month, int day, int year) { int numofdays; if (year<=2008) { dyear=year;...
Write the missing statements for the following program. #include <iostream> using namespace std; int main(void) { int Num1; cout << "Enter 2 numbers: "; cin >> Num2; if (Num1 < Num2) cout << "Smallest number is " << Num1; else cout << "Smallest number is " << Num2; return 0; }