Homework Soursec program I need to sort arrays using an insertion sort and
c++ program: I need to sort arrays using an insertion sort and a merge sort (I already have). I need to use these sorting methods to sort input arrays in the form of randomly generated numbers in the size of 20, 100 and 200. So I need 3 randomily generated arrays and sorted and outputed by both sorting method. I currently have it as given arrays and need help changing them to randomily generated arrays
Here is my code so far:
#include <iostream>
using namespace std;
void InsertionSort(int arr[],int size){
int temp,j;
for(int i=0; i<size; i++){
temp = arr[i];
j = i-1;
while((temp<arr[j]) && j>=0){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
}
//Merges two sub-arrays. First sub-array is arr[l..m],second is arr[m+1..r]
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 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++;
}
}
//l is left index and r is right index of the sub-array of array to be sorted
void MergeSort(int arr[], int l, int r){
if (l < r){
// Same as (l+r)/2, but avoids overflow for large l and h
int m = l+(r-l)/2;
// Sort first and second halves
MergeSort(arr, l, m);
MergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
void printArray(int arr[], int size){//Function to print array
int i;
for (i=0; i < size; i++)
cout << arr[i] <<\" \";
cout << endl;
}
int main(){
int size = 20;
int array1[] = {17,33,88,54,96,82,12,36,69,74,79,66,32,11,1,98,76,55,3,4};
int array2[] = {20,1,19,2,18,3,17,4,16,5,15,6,14,7,13,8,12,9,11,10};
int array3[] = {220,209,198,187,176,165,154,143,132,121,110,99,88,77,66,55,44,33,22,11};
int array4[] = {15,35,85,100,40,90,70,65,25,5,10,30,55,75,80,95,20,45,50,60};
int array5[] = {100,99,98,97,96,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81};
//Output for array1
cout << \"Original array 1: \ \";
printArray(array1, size);
InsertionSort(array1, size);
cout << \"Array 1 sorted by INSERTION SORT: \ \";
printArray(array1, size);
cout << \"\ \";
//Output for array2
cout << \"Original array 2: \ \";
printArray(array2, size);
MergeSort(array2,0,size);
cout << \"Array 2 sorted by MERGE SORT: \ \";
printArray(array2, size);
cout << \"\ \";
//Output for array3
cout << \"Original array 3: \ \";
printArray(array3, size);
InsertionSort(array3, size);
cout << \"Array 3 sorted by INSERTION SORT: \ \";
printArray(array3, size);
cout << \"\ \";
//Output for array4
cout << \"Original array 4: \ \";
printArray(array4, size);
MergeSort(array4,0,size);
cout << \"Array 4 sorted by MERGE SORT: \ \";
printArray(array4, size);
cout << \"\ \";
//Output for array5
cout << \"Original array 5: \ \";
printArray(array5, size);
InsertionSort(array5, size);
cout << \"Array 5 sorted by INSERTION SORT: \ \";
printArray(array5, size);
return 0;
}
Solution
#include <iostream>
using namespace std;
void InsertionSort(int arr[],int size){
int temp,j;
for(int i=0; i<size; i++){
temp = arr[i];
j = i-1;
while((temp<arr[j]) && j>=0){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
}
//Merges two sub-arrays. First sub-array is arr[l..m],second is arr[m+1..r]
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 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++;
}
}
//l is left index and r is right index of the sub-array of array to be sorted
void MergeSort(int arr[], int l, int r){
if (l < r){
// Same as (l+r)/2, but avoids overflow for large l and h
int m = l+(r-l)/2;
// Sort first and second halves
MergeSort(arr, l, m);
MergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
void printArray(int arr[], int size){//Function to print array
int i;
for (i=0; i < size; i++)
cout << arr[i] <<\" \";
cout << endl;
}
int main(){
int size = 20;
int array1[] = {17,33,88,54,96,82,12,36,69,74,79,66,32,11,1,98,76,55,3,4};
int array2[] = {20,1,19,2,18,3,17,4,16,5,15,6,14,7,13,8,12,9,11,10};
int array3[] = {220,209,198,187,176,165,154,143,132,121,110,99,88,77,66,55,44,33,22,11};
int array4[] = {15,35,85,100,40,90,70,65,25,5,10,30,55,75,80,95,20,45,50,60};
int array5[] = {100,99,98,97,96,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81};
int i;
int a[20];
for(i=0;i<20;i++)
a[i]=rand();
printArray(a,20);
//Output for array1
cout << \"Original array 1: \ \";
printArray(array1, size);
InsertionSort(array1, size);
cout << \"Array 1 sorted by INSERTION SORT: \ \";
printArray(array1, size);
cout << \"\ \";
//Output for array2
cout << \"Original array 2: \ \";
printArray(array2, size);
MergeSort(array2,0,size);
cout << \"Array 2 sorted by MERGE SORT: \ \";
printArray(array2, size);
cout << \"\ \";
//Output for array3
cout << \"Original array 3: \ \";
printArray(array3, size);
InsertionSort(array3, size);
cout << \"Array 3 sorted by INSERTION SORT: \ \";
printArray(array3, size);
cout << \"\ \";
//Output for array4
cout << \"Original array 4: \ \";
printArray(array4, size);
MergeSort(array4,0,size);
cout << \"Array 4 sorted by MERGE SORT: \ \";
printArray(array4, size);
cout << \"\ \";
//Output for array5
cout << \"Original array 5: \ \";
printArray(array5, size);
InsertionSort(array5, size);
cout << \"Array 5 sorted by INSERTION SORT: \ \";
printArray(array5, size);
return 0;
}
