Hello, I want to check if my C++ code is correct and follows the requeriments described thanks.
Requeriments:
Assignment Sorting
Benchmark each of the sorting methods listed below.
Insertion Sort
Bubble Sort
Selection Sort
Heap Sort.
Quick Sort.
Merge Sort.
Benchmark each of the above sorting methods for data sizes of
10000, 20000, 30000, 40000 and 50000. Display the results in a
table as shown below. The table should have rows and columns.
However, the rows and columns need not be separated by lines. Add
two more columns for Selection and Insertion Sorts
|
Data Size |
Heap Sort Time In Seconds |
Merge Sort Time In Seconds |
Quick Sort Time In Seconds |
Bubble Sort |
|
100000 |
||||
|
200000 |
||||
|
300000 |
||||
|
400000 |
||||
|
500000 |
Notes:
Do not use a local array for keeping data values. Use a global array for this purpose. You can use dynamically allocated arrays if you wish.
Generate the data using a random generator and store it in a global array for use in sorting. If you use a local array of large size, you will run out of stack space.
Calculate the time taken by a sort routine in seconds as below:
Code:
#include <iostream>
#include <ctime>
#include <cstdlib>
#include<iomanip>
#include<math.h>
using namespace std;
int *ins_el;
int *bubble_el;
int *sel_el;
int *heap_el;
int *quick_el;
int *merge_el;
void insertionSort(int n)
{
int i, j;
int temp;
for (i = 1; i <= n; i++)
{
temp = ins_el[i];
j = i - 1;
while (j > 0 && ins_el[j] > temp)
{
ins_el[j + 1] = ins_el[j];
j = j - 1;
}
ins_el[j + 1] = temp;
}
}
void bubbleSort(int n)
{
int i, j;
for (i = 0; i < n - 1; i++)
{
for (j = 0; j < n - i - 1; j++)
{
if (bubble_el[j] > bubble_el[j + 1])
{
int t = bubble_el[j];
bubble_el[j] = bubble_el[j + 1];
bubble_el[j + 1] = t;
}
}
}
}
void selectionSort(int n)
{
int i, j;
for (i = 0; i < n; i++)
{
for (j = i; j < n; j++)
{
if (sel_el[i] > sel_el[j])
{
int temp = sel_el[i];
sel_el[i] = sel_el[j];
sel_el[j] = temp;
}
}
}
}
void heapify(int n, int i)
{
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && heap_el[l] > heap_el[largest])
largest = l;
if (r < n && heap_el[r] > heap_el[largest])
largest = r;
if (largest != i)
{
int temp = heap_el[i];
heap_el[i] = heap_el[largest];
heap_el[largest] = temp;
heapify(n, largest);
}
}
void heapSort(int n)
{
int i = 0;
for (i = n; i >= 0; i--)
heapify(n, i);
for (i = n; i > 0; i--)
{
int temp = heap_el[0];
heap_el[0] = heap_el[i];
heap_el[i] = temp;
heapify(i, 0);
}
}
int partition(int low, int high)
{
int pivot = quick_el[high];
int i = (low - 1), j;
for (j = low; j <= high - 1; j++)
{
if (quick_el[j] <= pivot)
{
i++;
int temp = quick_el[i];
quick_el[i] = quick_el[j];
quick_el[j] = temp;
}
}
int temp = quick_el[i + 1];
quick_el[i + 1] = quick_el[high];
quick_el[high] = temp;
return (i + 1);
}
void quickSort(int low, int high)
{
if (low < high)
{
int pi = partition(low, high);
quickSort(low, pi - 1);
quickSort(pi + 1, high);
}
}
void merge(int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int *L = new int[n1];
int *R = new int[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = merge_el[l + i];
for (j = 0; j < n2; j++)
R[j] = merge_el[m + 1 + j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
merge_el[k] = L[i];
i++;
}
else
{
merge_el[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
merge_el[k] = L[i];
i++;
k++;
}
while (j < n2)
{
merge_el[k] = R[j];
j++;
k++;
}
}
void mergeSort(int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
// Sort first and second halves
mergeSort(l, m);
mergeSort(m + 1, r);
merge(l, m, r);
}
}
int main()
{
srand(time(NULL));
cout << left << setw(20) << "Data Size"
<< setw(15) << "Heap Sort"
<< setw(15) << "Merge Sort"
<< setw(15) << "Quick Sort"
<< setw(15) << "Bubble Sort"
<< setw(15) << "Selection Sort"
<< setw(16) << "Insertion Sort"
<< endl;
int rand_val;
/**Loop for 10000 to 50000*/
for (int i = 10000; i <= 50000; i += 10000)
{
ins_el = new int[i];
bubble_el = new int[i];
sel_el = new int[i];
heap_el = new int[i];
quick_el = new int[i];
merge_el = new int[i];
for (int j = 0; j < i; j++)
{
rand_val = rand() % 100;
ins_el[j] = rand_val;
bubble_el[j] = rand_val;
heap_el[j] = rand_val;
quick_el[j] = rand_val;
merge_el[j] = rand_val;
}
clock_t start, finish;
start = clock(); //time in milliseconds
heapSort(i);
finish = clock();
double heap_duration = (double)((finish - start) / (double)CLOCKS_PER_SEC); //time in secs.
start = clock(); //time in milliseconds
mergeSort(0, i - 1);
finish = clock(); //time in milliseconds
double merge_duration = (double)((finish - start) / (double)CLOCKS_PER_SEC); //time in secs.
start = clock(); //time in milliseconds
quickSort(0, i - 1);
finish = clock(); //time in milliseconds
double quick_duration = (double)((finish - start) / (double)CLOCKS_PER_SEC); //time in secs.
start = clock(); //time in milliseconds
bubbleSort(i);
finish = clock(); //time in milliseconds
//the constant CLOCKS_PER_SEC below is equal to 1000
double bubble_duration = (double)((finish - start) / (double)CLOCKS_PER_SEC); //time in secs.
start = clock(); //time in milliseconds
selectionSort(i);
finish = clock(); //time in milliseconds
//the constant CLOCKS_PER_SEC below is equal to 1000
double selection_duration = (double)((finish - start) / (double)CLOCKS_PER_SEC); //time in secs.
start = clock(); //time in milliseconds
insertionSort(i);
finish = clock(); //time in milliseconds
//the constant CLOCKS_PER_SEC below is equal to 1000
double insertion_duration = (double)((finish - start) / (double)CLOCKS_PER_SEC); //time in secs.
cout << left << setw(20) << i
<< setw(15) << heap_duration
<< setw(15) << merge_duration
<< setw(15) << quick_duration
<< setw(15) << bubble_duration
<< setw(15) << selection_duration
<< setw(16) << insertion_duration
<< endl;
}
system("pause");
return 0;
}
Picture:
Homework Answers
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
// Pointer declaration
int *ins_el;
int *bubble_el;
int *sel_el;
int *heap_el;
int *quick_el;
int *merge_el;
// Function to generate random numbers and stores it in
arrays
void generateArray(int size)
{
// Dynamically allocates memory of size MAX
ins_el = new int[size];
bubble_el = new int[size];
sel_el = new int[size];
heap_el = new int[size];
quick_el = new int[size];
merge_el = new int[size];
// srand for time
srand((unsigned)time(0));
// Loops MAX times
for(int x = 0; x < size; x++)
{
// Generates random number between 1 and MAX
// and stores it in x index position
ins_el[x] = (rand() % size)+1;
bubble_el[x] = (rand() % size)+1;
sel_el[x] = (rand() % size)+1;
heap_el[x] = (rand() % size)+1;
quick_el[x] = (rand() % size)+1;
merge_el[x] = (rand() % size)+1;
}// End of for loop
}// End of function
void insertionSort(int n)
{
int i, j;
int temp;
for (i = 1; i <= n; i++)
{
temp = ins_el[i];
j = i - 1;
while (j > 0 && ins_el[j] > temp)
{
ins_el[j + 1] = ins_el[j];
j = j - 1;
}
ins_el[j + 1] = temp;
}
}
void bubbleSort(int n)
{
int i, j;
for (i = 0; i < n - 1; i++)
{
for (j = 0; j < n - i - 1; j++)
{
if (bubble_el[j] > bubble_el[j + 1])
{
int t = bubble_el[j];
bubble_el[j] = bubble_el[j + 1];
bubble_el[j + 1] = t;
}
}
}
}
void selectionSort(int n)
{
int i, j;
for (i = 0; i < n; i++)
{
for (j = i; j < n; j++)
{
if (sel_el[i] > sel_el[j])
{
int temp = sel_el[i];
sel_el[i] = sel_el[j];
sel_el[j] = temp;
}
}
}
}
void heapify(int n, int i)
{
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && heap_el[l] > heap_el[largest])
largest = l;
if (r < n && heap_el[r] > heap_el[largest])
largest = r;
if (largest != i)
{
int temp = heap_el[i];
heap_el[i] = heap_el[largest];
heap_el[largest] = temp;
heapify(n, largest);
}
}
void heapSort(int n)
{
int i = 0;
for (i = n; i >= 0; i--)
heapify(n, i);
for (i = n; i > 0; i--)
{
int temp = heap_el[0];
heap_el[0] = heap_el[i];
heap_el[i] = temp;
heapify(i, 0);
}
}
int partition(int low, int high)
{
int pivot = quick_el[high];
int i = (low - 1), j;
for (j = low; j <= high - 1; j++)
{
if (quick_el[j] <= pivot)
{
i++;
int temp = quick_el[i];
quick_el[i] = quick_el[j];
quick_el[j] = temp;
}
}
int temp = quick_el[i + 1];
quick_el[i + 1] = quick_el[high];
quick_el[high] = temp;
return (i + 1);
}
void quickSort(int low, int high)
{
if (low < high)
{
int pi = partition(low, high);
quickSort(low, pi - 1);
quickSort(pi + 1, high);
}
}
void merge(int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int *L = new int[n1];
int *R = new int[n2];
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
L[i] = merge_el[l + i];
for (j = 0; j < n2; j++)
R[j] = merge_el[m + 1 + j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
merge_el[k] = L[i];
i++;
}
else
{
merge_el[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
merge_el[k] = L[i];
i++;
k++;
}
while (j < n2)
{
merge_el[k] = R[j];
j++;
k++;
}
}
void mergeSort(int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
// Sort first and second halves
mergeSort(l, m);
mergeSort(m + 1, r);
merge(l, m, r);
}
}
int main()
{
srand(time(NULL));
double start;
double finish;
// Declares double array to store sorting time for each sort
double heap_duration[5];
double merge_duration[5];
double quick_duration[5];
double bubble_duration[5];
double selection_duration[5];
double insertion_duration[5];
// Creates an array for different array size
int ArraySize[] = {10000, 20000, 30000, 40000, 50000};
// Loops 5 time for different size
for(int c = 0; c < 5; c++)
{
generateArray(ArraySize[c]);
start = clock(); //time in milliseconds
heapSort(ArraySize[c]);
finish = clock(); //time in milliseconds
heap_duration[c] = (double)((finish - start) / CLOCKS_PER_SEC);
//time in secs.
start = clock(); //time in milliseconds
mergeSort(0, ArraySize[c] - 1);
finish = clock(); //time in milliseconds
merge_duration[c] = (double)((finish - start) / CLOCKS_PER_SEC);
//time in secs.
start = clock(); //time in milliseconds
quickSort(0, ArraySize[c] - 1);
finish = clock(); //time in milliseconds
quick_duration[c] = (double)((finish - start) / CLOCKS_PER_SEC);
//time in secs.
start = clock(); //time in milliseconds
bubbleSort(ArraySize[c]);
finish = clock(); //time in milliseconds
//the constant CLOCKS_PER_SEC below is equal to 1000
bubble_duration[c] = (double)((finish - start) / CLOCKS_PER_SEC);
//time in secs.
start = clock(); //time in milliseconds
selectionSort(ArraySize[c]);
finish = clock(); //time in milliseconds
//the constant CLOCKS_PER_SEC below is equal to 1000
selection_duration[c] = (double)((finish - start) /
CLOCKS_PER_SEC); //time in secs.
start = clock(); //time in milliseconds
insertionSort(ArraySize[c]);
finish = clock(); //time in milliseconds
//the constant CLOCKS_PER_SEC below is equal to 1000
insertion_duration[c] = (double)((finish - start) /
CLOCKS_PER_SEC); //time in secs.
}// End of for loop
// Displays heading
cout<<"\nData Size \tHeap Sort \tMerge Sort \tQuick Sort
\tBubble Sort \tSelection Sort \tInsertion Sort\n";
// Loops 5 times for displaying time taken for each sorting
for(int c = 0; c < 5; c++)
{
cout<<ArraySize[c]<<"\t\t"<<heap_duration[c]<<"\t\t"<<merge_duration[c]<<"\t\t"<<quick_duration[c];
\
cout<<"\t\t"<<bubble_duration[c]<<"\t\t"<<selection_duration[c]<<"\t\t"<<insertion_duration[c]<<endl;
}// End of for loop
return 0;
}// End of main function
Sample Output:
Data Size Heap Sort Merge Sort Quick Sort Bubble Sort Selection
Sort Insertion Sort
10000 0.004 0.013 0.002 0.358 0.381 0.112
20000 0.005 0.015 0.003 1.367 1.893 0.776
30000 0.008 0.021 0 3.105 3.363 0.969
40000 0.011 0.03 0.006 5.773 5.754 1.726
50000 0.015 0.037 0.008 9.053 8.942 2.552
Add Answer to:
Hello, I want to check if my C++ code is correct and follows the
requeriments described...
How would I be able to get a Merge Sort to run in this code? MY...
How would I be able to get a Merge Sort to run in this code? MY CODE: #include <iostream> #include <fstream> #include <stdlib.h> #include <stdio.h> #include <time.h> using namespace std; class mergersorter { private: float array[1000] ; int n = 1000; int i=0; public: void fillArray() { for(i=1;i<=n;i++) { array[i-1]= ( rand() % ( 1000) )+1; } } void arrayout () { ...
Merge Sort: Time Complexity: O(n log(n)) #include "stdafx.h" #include <iostream> #include <time.h> #include <stdlib.h> using namespace...
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 { ...
use the same code. but the code needs some modifications. so use this same code and...
use the same code. but the code needs some modifications. so
use this same code and modify it and provide a output
Java Program to Implement Merge Sort import java.util.Scanner Class MergeSort public class MergeSort Merge Sort function / public static yoid sortfintfl a, int low, int high) int N-high-low; if (N1) return; int mid- low +N/2; Il recursively sort sort(a, low, mid); sort(a, mid, high); I/ merge two sorted subarrays int] temp new int[N]; int i- low, j-mid; for...
The following C code keeps returning a segmentation fault! Please debug so that it compiles. Also...
The following C code keeps returning a segmentation fault! Please debug so that it compiles. Also please explain why the seg fault is happening. Thank you #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> // @Name loadMusicFile // @Brief Load the music database // 'size' is the size of the database. char** loadMusicFile(const char* fileName, int size){ FILE *myFile = fopen(fileName,"r"); // Allocate memory for each character-string pointer char** database = malloc(sizeof(char*)*size); unsigned int song=0; for(song =0; song < size;...
I want to compare the runtimes and swap operations times among quick Sort, selection Sort and...
I want to compare the runtimes and swap operations times among quick Sort, selection Sort and shell Sort here is my code: But when I create a 1000,000 size array, I can't get the result of the operations times and runtime. what's wrong with my code? and I also want to copy the array. Because I want to use same array for three sort. And for the shell Sort, I haven't learn it in my class. Can anyone help me...
My following program has an array which holds 1000 random integers between 1-1000. Now I need...
My following program has an array which holds 1000 random integers between 1-1000. Now I need help to create an array that holds 10,000 random integer between 1-1000 in my following program. The main goal of this program is time analysis by using bubble sort and binary search algorithms. Please do the following task; 1. Replace the 1000 random integers with 10,000 random integers After change please answer the following question 2. what will be happen, if an array holds...
In this assignment you will implement merge-sort algorithm by creating 2 threads instead of 2 pro...
In this assignment you will implement merge-sort algorithm by creating 2 threads instead of 2 processes. First half of the array will be sorted by thread 1 and the second half by thread 2. When the threads complete their tasks, the main program will merge the half arrays. You should not waste your time on merge-sort algorithm. Use the merge sort algorithm given below void mergesort(int a[],int i,int j) { int mid; if(i<j) { mid=(i+j)/2; mergesort(a,i,mid); //left recursion mergesort(a,mid+1,j); //right...
I need to program 3 and add to program 2 bellows: Add the merge sort and...
I need to program 3 and add to program 2 bellows: Add the merge sort and quick sort to program 2 and do the same timings, now with all 5 sorts and a 100,000 element array. Display the timing results from the sorts. DO NOT display the array. ____________________>>>>>>>>>>>>>>>>>>>>___________________________ (This is program 2 code that I did : ) ---->>>>>> code bellow from program 2 java program - Algorithms Write a program that randomly generates 100,000 integers into an array....
Please give a output Linux/Ubuntu and how to run it (compile) this program ,my assigment is below...
Please give a output Linux/Ubuntu and how to run it (compile) this program ,my assigment is below : : Merge Sort algorithm using 2 processes a.) Define an integer array of 100 integers. Populate this array with random numbers. You can use int rand(void); function. Do not forget to initialize this function. You will sort the numbers in the array using merge-sort algorithm. In merge sort algorithm the half of the array will be sorted by one process and second...
use the same code. but the code needs some modifications. so
use this same code and modify it and provide a output
Java Program to Implement Merge Sort import java.util.Scanner Class MergeSort public class MergeSort Merge Sort function / public static yoid sortfintfl a, int low, int high) int N-high-low; if (N1) return; int mid- low +N/2; Il recursively sort sort(a, low, mid); sort(a, mid, high); I/ merge two sorted subarrays int] temp new int[N]; int i- low, j-mid; for...
Most questions answered within 3 hours.
-
Let M = 8.00kg, m = 6.00kg, θ = 40.00, and the coefficient of
kinetic friction...
asked 1 minute ago -
Java. For C through H True or false?
c. Primitive variables must be objects.
d. Integer...
asked 6 minutes ago -
Write a program that turns a 32-bit numeric value (e.g.,
0xFFFFh) and converts it to a...
asked 7 minutes ago -
A motor produces a torque of 0.25 N m at an angular velocity of
7200 revolutions...
asked 21 minutes ago -
***Please answer the below java question***
Are static methods inheritable? Can they be overridden?
asked 23 minutes ago -
In reaching her destination, a backpacker walks with an average
velocity of 1.13 m/s, due west....
asked 23 minutes ago -
Write two C programs that run a
server program and a client program concurrently.
Server program:...
asked 22 minutes ago -
Executive Program Practical Connection Assignment
Subject : Operations Security.
Assignment:
Provide a reflection of at least...
asked 32 minutes ago -
Every time Casey is at bat he has a 0.4 probability of
getting on base (assume...
asked 41 minutes ago -
The Walston Company is to be liquidated and has the following
liabilities:
Income taxes
$
9,400...
asked 48 minutes ago -
If
the more comprehensive data is available in MEPS, why does the NHIS
still exist? How...
asked 1 hour ago -
Koo argues that the Japanese economy in the 1990s suffered from
a balance sheet recession. What...
asked 1 hour ago