Merge Sort


1. Algorithm

Describe the problem: the two lists A and B respectively have m and n elements arranged in order. Mixing problem poses two lists A and B together into a list C is an unordered list.
Step 1: initialize three runs in the loop index i = 0, j = 0, k = 0 corresponds to the three arrays A, B and C.
Step 2: at each step if both indicators (i <m and j <n) we select min (A [i], B [j]) and save it in C [k]. Proceed to Step 4.
Step 3: increase value k 1 and return to step 2.
Step 4: Copy all of the remaining value from the list that indicators also violated (ie i <m or j <m) in the array C.

merge_sort_exam

2. Source Code

#include <iostream>
#include <conio.h>
#define max 100
using namespace std;
//Input Array
void InputArray(int A[],int n){
for(int i=0; i<n; i++) {
cout<<"Input element A["<<i<<"] =";
cin>>A[i];
}
}

//Print Array
void PrintArray(int A[],int n){
cout<<endl;
for(int i=0; i<n; i++)
cout<<A[i]<<"\t";
}
//Swap 2 elements
void Swap(int &a,int &b) {
int temp = a;
a = b;
b = temp;
}
//Merge Sort Algorithm
void MergeSort(int m, int n, int &k, int A[], int B[], int C[]) {
int i = 0, j = 0;
k = 0;
while (i < m && j < n) {
if (A[i] <= B[j]) {
C[k] = A[i];
i++;
}else {
C[k] = B[j];
j++;
}
k++;
}
if (i < m){
for (int p = i; p < m; p++){
C[k] = A[p];
k++;
}
} else {
for (int p = j; p < n; p++) {
C[k] = B[p];
k++;
}
}
}
//Main Function
int main() {
int A[max],B[max],C[max],n,m,k;
cout<<"m = "; cin>>m;
cout<<"n = "; cin>>n;
cout<<"Enter unordered list A:\n";
InputArray(A,m);
cout<<"Enter unordered list tu B:\n";
InputArray(B,n);
cout<<"\nMerge Sort 2 array A, B\n";
MergeSort(m,n,k,A,B,C);
PrintArray(C,k);
getch();
return 0;
}

3. Result

selection_sort_result


Advertisements