void insertion_sort(int array[], int length, int & count_comp, int & count_move);
void merge_sort(int array[], int length, int & count_comp, int & count_move);
void heap_sort(int array[], int length, int & count_comp, int & count_move);
void quick_sort_sort(int array[], int length, int & count_comp, int & count_move);
// YOUR
// Implementation
// should
// go
// here
// or be put in separated .cpp files
typedef void (*sort_algo_type)(int array[], int length, int& count_comp, int & count_move);
void run_sort_algo(int array[], int length, sort_algo_type sorting, const char* algo_name, const char* data_file_name)
{
int count_comparison = 0;
int count_move = 0;
clock_t start,end;
start = clock();
sorting(array, length, count_comparison, count_move);
end=clock();
//double duration = (double)(end - start) *1000 / CLOCKS_PER_SEC;
long duration = end - start; // Just use clock cycles
printf("Sorting algo summary, %s, %s, data size %d, count_comp %d, count_move %d, time %ld cycles\n", algo_name, data_file_name, length, count_comparison, count_move, duration);
printf("Showing sorted result");
for(int i = 0; i < length; i++)
printf(", %d", array[i]);
printf("\n");
}
int main(int argc, char** argv)
{
// read the data
if(argc < 2) //
{
printf("Usage: %s data_file_1 data_file_2 ...\n", argv[0]);
exit(1);
}
const int num_files = argc - 1;
std::vector raw_data;
for(int i=0; i < num_files; i++)
{
const char* data_filename = argv[i+1];
std::ifstream infile(data_filename);
// clear raw_data
raw_data.clear();
// assume one number per line
int d;
while(infile.good())
{
infile >> d;
raw_data.push_back(d);
}
// Now run different sorting algos
std::vector tmp_data(raw_data.begin(), raw_data.end());
run_sort_algo(&tmp_data[0], raw_data.size(), insertion_sort, "InsertionSort", data_filename);
//overwrite tmp_data for another sorting
tmp_data.assign(raw_data.begin(), raw_data.end());
run_sort_algo(&tmp_data[0], raw_data.size(), merge_sort, "MergeSort", data_filename);
// overwrite tmp_data for another sorting
tmp_data.assign(raw_data.begin(), raw_data.end());
run_sort_algo(&tmp_data[0], raw_data.size(), heap_sort, "HeapSort", data_filename);
// overwrite tmp_data for another sorting
tmp_data.assign(raw_data.begin(), raw_data.end());
run_sort_algo(&tmp_data[0], raw_data.size(), quick_sort, "QuickSort", data_filename);
}
}Answer:
#include<ctime>
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<fstream>
using namespace std;
void insertion_sort(int array[], int length, int & count_comp, int & count_move);
void merge_sort(int array[], int i,int length, int & count_comp, int & count_move);
void heap_sort(int array[], int length, int & count_comp, int & count_move);
void quick_sort(int array[], int i, int length, int & count_comp, int & count_move);
void insertion_sort(int arr[], int n ,int & count_comp, int & count_move)
{
int i, key, j;
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];
count_comp = count_comp + 1;
j = j - 1;
}
arr[j + 1] = key;
count_move = count_move + 1;
}
}
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r,int &count_comp,int &count_move)
{
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; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2)
{
count_comp = count_comp +1;
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)
{
count_comp = count_comp +1;
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there
are any */
while (j < n2)
{
count_comp = count_comp +1;
arr[k] = R[j];
j++;
k++;
}
count_move = count_move +1;
}
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void merge_sort(int arr[], int l, int r,int & count_comp, int & count_move)
{
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
merge_sort(arr, l, m,count_comp,count_move);
merge_sort(arr, m+1, r, count_comp, count_move);
merge(arr, l, m, r,count_comp,count_move);
}
}
// A utility function to swap two elements
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i,int & count_comp , int & count_move)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
{
largest = l;
count_comp = count_comp +1;
}
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
{
largest = r;
count_comp = count_comp +1;
}
// If largest is not root
if (largest != i)
{
int temp;
temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
count_comp = count_comp +1;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest,count_comp,count_move);
}
}
// main function to do heap sort
void heap_sort(int arr[], int n, int & count_comp, int & count_move)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i, count_comp,count_move);
// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
int temp;
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
count_move = count_move +1;// call max heapify on the reduced heap
heapify(arr, i, 0,count_comp,count_move);
}
}
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition (int arr[], int low, int high,int &count_comp,int &count_move)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
count_comp = count_comp +1;
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
count_move = count_move +1;
}
}
swap(&arr[i + 1], &arr[high]);
count_move = count_move +1;
return (i + 1);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quick_sort(int arr[], int low, int high, int & count_comp, int & count_move)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high,count_comp,count_move);
// Separately sort elements before
// partition and after partition
quick_sort(arr, low, pi - 1,count_comp,count_move);
quick_sort(arr, pi + 1, high,count_comp,count_move);
}
}
//typedef void (*sort_algo_type)(int array[], int length, int& count_comp, int & count_move);
void run_sort_algo(int array[], int length, const char* algo_name, const char* data_file_name)
{
int count_comparison = 0;
int count_move = 0;
clock_t start = clock();
if(algo_name[0] == 'I')
insertion_sort(array,length,count_comparison,count_move);
if(algo_name[0] == 'M')
merge_sort(array, 0,length, count_comparison, count_move);
if(algo_name[0] == 'H')
heap_sort(array,length,count_comparison,count_move);
if(algo_name[0] == 'Q')
quick_sort(array,0,length,count_comparison,count_move);
clock_t end=clock();
//double duration = (double)(end - start) *1000 / CLOCKS_PER_SEC;
long duration = end - start; // Just use clock cycles
printf("Sorting algo summary, %s, %s, data size %d, count_comp %d, count_move %d, time %ld cycles\n", algo_name, data_file_name, length, count_comparison, count_move, duration);
printf("Showing sorted result");
for(int i = 0; i < length; i++)
printf(", %d", array[i]);
printf("\n");
}
int main(int argc, char** argv)
{
// read the data
if(argc < 2) //
{
printf("Usage: %s data_file_1 data_file_2 ...\n", argv[0]);
exit(1);
}
const int num_files = argc - 1;
std::vector<int> raw_data;
for(int i=0; i < num_files; i++)
{
const char* data_filename = argv[i+1];
std::ifstream infile(data_filename);
// clear raw_data
raw_data.clear();
// assume one number per line
int d;
while(infile.good())
{
infile >> d;
raw_data.push_back(d);
}
// Now run different sorting algos
std::vector<int> tmp_data(raw_data.begin(), raw_data.end());
run_sort_algo(&tmp_data[0], raw_data.size(), "InsertionSort", data_filename);
//overwrite tmp_data for another sorting
tmp_data.assign(raw_data.begin(), raw_data.end());
run_sort_algo(&tmp_data[0], raw_data.size(),"MergeSort", data_filename);
// overwrite tmp_data for another sorting
tmp_data.assign(raw_data.begin(), raw_data.end());
run_sort_algo(&tmp_data[0], raw_data.size(),"HeapSort", data_filename);
// overwrite tmp_data for another sorting
tmp_data.assign(raw_data.begin(), raw_data.end());
run_sort_algo(&tmp_data[0], raw_data.size(),"QuickSort", data_filename);
}
}
void insertion_sort(int array[], int length, int & count_comp, int & count_move); void merge_sort(int array[], int length, int & count_comp, int & count_move); void heap_sort(int array...
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;...
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 { ...
If void * is a pointer to void is a "generic" pointer type, and a void * can be converted to any other pointer type * without an explicit cast, why in the ,myarrcopy function the malloc is created like char and not like void? if we are going to work with different type of arrays? Here is de program: *This is a function that make a copy of any given array. * We then use this function make a...
In Programming language C - How would I convert my words char array into a string array so I can use the strcmp() function and alphabetically sort the words? #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> int main(int argc, char*argv[]){ int i =0; int j =0; int count =0; int length = strlen(argv[1]); for(i =0; i < length; i++){ if(isalpha(argv[1][i]) == 0 ||isdigit(argv[1][i] != 0)){ count ++; } printf("%c",argv[1][i]); } char *strings; int wordNum =0; int charNum =0; strings...
I have the following code in C: void sighandler(int sig) { printf("exiting child..."); } int main(int argc,char* argv[]) { if(argc > 1) { char* commandName; for(int i=2;i { forkChild = fork(); signal(SIGINT,sighandler); if(forkChild == 0) { execlp(commandName,commandName,argv[i],NULL); exit(0); } else { wait(NULL); } } My problem is that I would like to kill the child with ^C but leave the parent running....
graph binary search for size and time c++ //System Libraries #include <iostream> #include <string> #include <cstdlib> #include <ctime> #include <iomanip> #include <algorithm> using namespace std; //User Libraries //Global Constants, no Global Variables are allowed //Math/Physics/Conversions/Higher Dimensions - i.e. PI, e, etc... //Function Prototypes //Execution Begins Here! int main(int argc, char** argv) { int n, i, arr[50], search, first, last, middle,count=0,count_in,tot; clock_t start, end; float duration; cout<<"Enter total number of elements :"; cin>>n; cout<<"Enter numbers"; for (i=0; i<n;i++) cin>>arr[i]; cout<<"Enter a...
The provided code is my solution, stripped of the details needed to make it work. It is not a “good” program. It lives in a single file, does not use classes, and it has those evil global variables. That is by design. I want to to craft code. Use my code as a guide to help you put together the needed parts. #include #include #include // defaults const int MAX_STEPS = 100; // how long do we run the simulation...
#include <stdio.h> int main(int argc, char *argv[]) { int i; for (i = argc - 1; i > 0; i--) printf("%s ", argv[i]); printf("\n"); return 0; } can you explain this code in c and why use this function
#include <stdio.h> #include <string.h> #include <ctype.h> #include <stdlib.h> int main(void) { /* Type your code here. */ int GetNumOfNonWSCharacters(const char usrStr[]) { int length; int i; int count = 0; char c; length=strlen(usrStr); for (i = 0; i < length; i++) { c=usrStr[i]; if ( c!=' ' ) { count++; } } return count; } int GetNumOfWords(const char usrStr[]) { int counted = 0; // result // state: const char* it = usrStr; int inword = 0; do switch(*it)...
#include<stdio.h> #include<stdio.h> int main(){ int i; //initialize array char array[10] = {“Smith”, “Owen”, “Kowalczyk”, “Glass”, “Bierling”, “Hanenburg”, “Rhoderick”, “Pearce”, “Raymond”, “Kamphuis”}; for(int i=0; i<8;i++){ for(int j=0; j<9; j++){ if(strcmp(array[j],array[j+1])>0){ char temp[20]; strcpy(temp,array[j]); strcpy(array[j],array[j+1]); strcpy(array[j+1],temp); } } } printf(“---------File Names---------\n”); for(inti=0; i<9; i++){ printf(“\t%s\n”,array[i]); } printf(-------5 Largest Files according to sorting----\n”); for(int i=0;i>=5;i--) { printf(“\t%s\n”,array[i]); } return0; } Consider the "sort" program (using with void* parameters in the bubblesort function) from the week 10 "sort void" lecture. Modify it as follows...