QuestionQuestion

It is your job to explain how the three different sorting algorithms work, why they have a specific theoretical worst time complexity (Big O), and compare and contrast the theoretical worst time complexity with experimental data.
Your paper must include:
• Function Header for each sorting algorithm (bubble_sort, insertion_sort,
selection_sort, merge_sort and merge).
/***********************************************************************
* Description:
* Parameters:
* Returns:
* Pre-Conditions:
* Post-Conditions:
***********************************************************************/
• Very Thorough Description of each sorting algorithm (bubble_sort, insertion_sort, and selection_sort).
o How does the algorithm work? (Text and pictures are required. Pictures cannot be taken from the internet, they can be drawn on computer or pictures of drawings.)
o What does the code do? (Answer each question/comment in the code provided and summarize them in your paper)
• A table with at least 15 or more test cases for timing and experimenting with the sorting algorithms:

Input Values Sorting Algorithm Big O Complexity Time for N:
Empty file Bubble Sort O(N^2) N=0, 0 microseconds


Compare and contrast the expected time based on the Big O complexity and data size, N, with the actual experimental time for each sorting algorithm with a data size N and the data arrangement.

o How big did your N have to be to get timings you could use?
o What did you data look like?
o Do the times match what you expected?
o Does it make any difference whether the data items are in reverse sorted order (worst case) or already sorted (best case)?

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

//typedef struct timeval time;
void print_array(int *, int);
void merge(int *, int, int, int);
void merge_sort(int *, int, int);
void selection_sort(int *, int);
void insertion_sort(int *, int);
void bubble_sort(int *, int);
void fill_array(int **, int *);
void add_num(int **, int *, int);

int main() {
    int *nums = NULL;
    int size = 0;
    struct timeval stop;
    struct timeval start;

    fill_array(&nums, &size);
    print_array(nums, size);

    //Time the function here
    gettimeofday(&start, NULL);

    //bubble_sort(nums, size);
   // insertion_sort(nums, size);
    //merge_sort(nums, 0, size-1);
    selection_sort(nums, size);

    gettimeofday(&stop, NULL);

    printf("MicroSeconds: %d\n", stop.tv_usec - start.tv_usec);
    //printf("Seconds: %d\n", stop.tv_sec-start.tv_sec);

    free(nums);

    return 0;
}

/*************************************************
* Description: This prints the contents of an array
* Params: array of integers and size of the array
* Returns: none
* Post-conditions: none
* Pre-conditions: size is accurate number of
*                elements in the array >=0
* **********************************************/
void print_array(int *nums, int size) {
    int i;

    printf("The array elements are:\n");
    for (i = 0; i < size; i++)
       printf("%d ", nums[i]);
    printf("\n\n");
// printf("\n");
}...

By purchasing this solution you'll be able to access the following files:
Solution.c and Solution.docx.

$108.00
for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available C-Family Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats