QuestionQuestion

1. Compose a sequential Bubble Sort program in C. Generate 5000 random integers.
Record the sequential running time of the BubbleSort on 5000 random integers.
Then partition the SAME 5000 integers into two halfs.
Record the sequential running time of the SAME program sorting the two halfs in sequence then mergeSort them.
Explain the timing differences.

2. (2 pts) Compose a dense square matrix multiplication program in C.
Generate two random 5x5 matrices and compute six matrix products using six different (i,j,k) orders.
Should all six results be identical? Explain.

3. (3 pts) Generate random 1000x1000 matrices and record six elapsed times using six different (I,j,k) orders.
Which order is the fastest and why?

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 <math.h>
#include <stdlib.h>
#include <time.h>
int comp = 0;//set a global variable as merge sort counter.

void merge(int [], int, int, int);

void insertionSort(int a[], int start, int n) {//use int start since in the merge sort we will have to split the array into 2 and then merge
    int i;
    int j;
    int key;
            
            int swap =0;
    //loop through all numbers
    for (i = start; i < n - 1; i++) {
                      key = a[i];//select a value to insert
                      j = i-1;//select position to insert
            while (j >= 0 && a[j] > key) { //check if the number selected to inserted is smaller than its previous number
            a[j + 1] = a[j];//if yes, swap the num
            j--;
          swap++;//count the swap
       }
       a[j + 1] = key;//start the next iteration to swap

    }
          printf("\nswap numbers for insertion sort is %d ", swap);

}
//indicate the left and right index of the array we want to sort
void mergeSort(int a[], int left, int right) {
    int midIndex;//make sure left is smaller the right
    if (left < right) {
       midIndex = (right + left) / 2;//find middle index and sort the sub array
       mergeSort(a, left, midIndex);
       mergeSort(a, midIndex + 1, right);
       merge(a, left, midIndex, right);
         
    }
         
}
//start the merge sort by sort 2 subarray, left array and right array separated by middle index
void merge(int a[], int left, int middle, int right) {
    int nl = middle - left + 1;
    int nr = right - middle;
    //create 2 temperate arrays
    int leftArr[nl];
    int rightArr[nr];

    int i;
    int j;
    int k;

         
    //copy data to to the temperate arrays from the original array
    for (i = 0; i < nl; i++) {
       leftArr[i] = a[left + i];
    }

    for (i = 0; i < nr; i++) {
       rightArr[i] = a[middle + 1 + i];
    }
    //merge the two splitted array together to the result array
    i = j = 0;
    k = left;...

By purchasing this solution you'll be able to access the following files:
A1.c and Archive.zip.

50% discount

Hours
Minutes
Seconds
$45.00 $22.50
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