Great Deal! Get Instant $10 FREE in Account on First Order + 10% Cashback on Every Order Order Now

cop3502-as3-sample-output.txt SORT SET: n = 50, all sorts, by weight Bubble sort 50 monsters by weight... Sort complete with 1225 comparisons and 523 swaps. 0.000077s CPU time used The list is sorted....

1 answer below »
cop3502-as3-sample-output.txt
SORT SET: n = 50, all sorts, by weight
Bu
le sort 50 monsters by weight...
Sort complete with 1225 comparisons and 523 swaps.
0.000077s CPU time used
The list is sorted.
Selection sort 50 monsters by weight...
Sort complete with 1274 comparisons and 47 swaps.
0.000030s CPU time used
The list is sorted.
Insertion sort 50 monsters by weight...
Sort complete with 746 comparisons and 44 block copies (1253 total copies).
0.000056s CPU time used
The list is sorted.
Quick sort 50 monsters by weight...
Sort complete with 229 comparisons and 97 swaps.
0.000016s CPU time used
The list is sorted.
Merge sort 50 monsters...
Sort complete with 221 comparisons, 98 block copies, 572 total copies, 49 mallocs.
0.000070s CPU time used
The list is sorted.
Merge-insertion sort 50 monsters...
Sort complete with 398 comparisons, 43 block copies, 742 total copies, 1 mallocs.
0.000020s CPU time used
The list is sorted.
SORT SET COMPLETE
SORT SET: n = 50, all sorts, by name
Bu
le sort 50 monsters by name...
Sort complete with 1225 comparisons and 608 swaps.
0.000098s CPU time used
The list is sorted.
Selection sort 50 monsters by name...
Sort complete with 1274 comparisons and 46 swaps.
0.000046s CPU time used
The list is sorted.
Insertion sort 50 monsters by name...
Sort complete with 658 comparisons and 41 block copies (1143 total copies).
0.000029s CPU time used
The list is sorted.
Quick sort 50 monsters by name...
Sort complete with 303 comparisons and 82 swaps.
0.000022s CPU time used
The list is sorted.
Merge sort 50 monsters...
Sort complete with 216 comparisons, 98 block copies, 572 total copies, 49 mallocs.
0.000048s CPU time used
The list is sorted.
Merge-insertion sort 50 monsters...
Sort complete with 351 comparisons, 41 block copies, 713 total copies, 1 mallocs.
0.000021s CPU time used
The list is sorted.
SORT SET COMPLETE
SORT SET: n = 500, all sorts, by weight
Bu
le sort 500 monsters by weight...
Sort complete with XXXXXXXXXXcomparisons and 60639 swaps.
0.006494s CPU time used
The list is sorted.
Selection sort 500 monsters by weight...
Sort complete with XXXXXXXXXXcomparisons and 495 swaps.
0.001587s CPU time used
The list is sorted.
Insertion sort 500 monsters by weight...
Sort complete with 64603 comparisons and 492 block copies XXXXXXXXXXtotal copies).
0.000949s CPU time used
The list is sorted.
Quick sort 500 monsters by weight...
Sort complete with 5024 comparisons and 2564 swaps.
0.000323s CPU time used
The list is sorted.
Merge sort 500 monsters...
Sort complete with 3861 comparisons, 998 block copies, 8976 total copies, 499 mallocs.
0.000378s CPU time used
The list is sorted.
Merge-insertion sort 500 monsters...
Sort complete with 4611 comparisons, 463 block copies, 9133 total copies, 31 mallocs.
0.000233s CPU time used
The list is sorted.
SORT SET COMPLETE
SORT SET: n = 500, all sorts, by name
Bu
le sort 500 monsters by name...
Sort complete with XXXXXXXXXXcomparisons and 62213 swaps.
0.009424s CPU time used
The list is sorted.
Selection sort 500 monsters by name...
Sort complete with XXXXXXXXXXcomparisons and 495 swaps.
0.004242s CPU time used
The list is sorted.
Insertion sort 500 monsters by name...
Sort complete with 63024 comparisons and 487 block copies XXXXXXXXXXtotal copies).
0.002259s CPU time used
The list is sorted.
Quick sort 500 monsters by name...
Sort complete with 4658 comparisons and 2384 swaps.
0.000391s CPU time used
The list is sorted.
Merge sort 500 monsters...
Sort complete with 3849 comparisons, 998 block copies, 8976 total copies, 499 mallocs.
0.000478s CPU time used
The list is sorted.
Merge-insertion sort 500 monsters...
Sort complete with 4603 comparisons, 459 block copies, 9100 total copies, 31 mallocs.
0.000341s CPU time used
The list is sorted.
SORT SET COMPLETE
SORT SET: n = 5000, all sorts, by weight
Bu
le sort 5000 monsters by weight...
Sort complete with XXXXXXXXXXcomparisons and XXXXXXXXXXswaps.
0.670259s CPU time used
The list is sorted.
Selection sort 5000 monsters by weight...
Sort complete with XXXXXXXXXXcomparisons and 4994 swaps.
0.166510s CPU time used
The list is sorted.
Insertion sort 5000 monsters by weight...
Sort complete with XXXXXXXXXXcomparisons and 4990 block copies XXXXXXXXXXtotal copies).
0.101287s CPU time used
The list is sorted.
Quick sort 5000 monsters by weight...
Sort complete with 70184 comparisons and 34619 swaps.
0.004460s CPU time used
The list is sorted.
Merge sort 5000 monsters...
Sort complete with 55260 comparisons, 9998 block copies, XXXXXXXXXXtotal copies, 4999 mallocs.
0.006112s CPU time used
The list is sorted.
Merge-insertion sort 5000 monsters...
Sort complete with 66743 comparisons, 4615 block copies, XXXXXXXXXXtotal copies, 255 mallocs.
0.003925s CPU time used
The list is sorted.
SORT SET COMPLETE
SORT SET: n = 5000, all sorts, by name
Bu
le sort 5000 monsters by name...
Sort complete with XXXXXXXXXXcomparisons and XXXXXXXXXXswaps.
0.905517s CPU time used
The list is sorted.
Selection sort 5000 monsters by name...
Sort complete with XXXXXXXXXXcomparisons and 4986 swaps.
0.415122s CPU time used
The list is sorted.
Insertion sort 5000 monsters by name...
Sort complete with XXXXXXXXXXcomparisons and 4989 block copies XXXXXXXXXXtotal copies).
0.227113s CPU time used
The list is sorted.
Quick sort 5000 monsters by name...
Sort complete with 67620 comparisons and 33329 swaps.
0.005186s CPU time used
The list is sorted.
Merge sort 5000 monsters...
Sort complete with 55251 comparisons, 9998 block copies, XXXXXXXXXXtotal copies, 4999 mallocs.
0.006659s CPU time used
The list is sorted.
Merge-insertion sort 5000 monsters...
Sort complete with 66666 comparisons, 4597 block copies, XXXXXXXXXXtotal copies, 255 mallocs.
0.004486s CPU time used
The list is sorted.
SORT SET COMPLETE
SORT SET: n = 50000, fast sorts only, by weight
Quick sort 50000 monsters by weight...
Sort complete with XXXXXXXXXXcomparisons and XXXXXXXXXXswaps.
0.059896s CPU time used
The list is sorted.
Merge sort 50000 monsters...
Sort complete with XXXXXXXXXXcomparisons, 99998 block copies, XXXXXXXXXXtotal copies, 49999 mallocs.
0.078171s CPU time used
The list is sorted.
Merge-insertion sort 50000 monsters...
Sort complete with XXXXXXXXXXcomparisons, 46349 block copies, XXXXXXXXXXtotal copies, 2047 mallocs.
0.049662s CPU time used
The list is sorted.
SORT SET COMPLETE
SORT SET: n = 50000, fast sorts only, by name
Quick sort 50000 monsters by name...
Sort complete with XXXXXXXXXXcomparisons and XXXXXXXXXXswaps.
0.075177s CPU time used
The list is sorted.
Merge sort 50000 monsters...
Sort complete with XXXXXXXXXXcomparisons, 99998 block copies, XXXXXXXXXXtotal copies, 49999 mallocs.
0.079564s CPU time used
The list is sorted.
Merge-insertion sort 50000 monsters...
Sort complete with XXXXXXXXXXcomparisons, 46317 block copies, XXXXXXXXXXtotal copies, 2047 mallocs.
0.062662s CPU time used
The list is sorted.
SORT SET COMPLETE
SORT SET: n = 500000, fast sorts only, by weight
Quick sort XXXXXXXXXXmonsters by weight...
Sort complete with XXXXXXXXXXcomparisons and XXXXXXXXXXswaps.
0.722573s CPU time used
The list is sorted.
Merge sort XXXXXXXXXXmonsters...
Sort complete with XXXXXXXXXXcomparisons, XXXXXXXXXXblock copies, XXXXXXXXXXtotal copies, XXXXXXXXXXmallocs.
0.933181s CPU time used
The list is sorted.
Merge-insertion sort XXXXXXXXXXmonsters...
Sort complete with XXXXXXXXXXcomparisons, XXXXXXXXXXblock copies, XXXXXXXXXXtotal copies, 32767 mallocs.
0.759191s CPU time used
The list is sorted.
SORT SET COMPLETE
SORT SET: n = 500000, fast sorts only, by name
Quick sort XXXXXXXXXXmonsters by name...
Sort complete with XXXXXXXXXXcomparisons and XXXXXXXXXXswaps.
0.867876s CPU time used
The list is sorted.
Merge sort XXXXXXXXXXmonsters...
Sort complete with XXXXXXXXXXcomparisons, XXXXXXXXXXblock copies, XXXXXXXXXXtotal copies, XXXXXXXXXXmallocs.
1.031811s CPU time used
The list is sorted.
Merge-insertion sort XXXXXXXXXXmonsters...
Sort complete with XXXXXXXXXXcomparisons, XXXXXXXXXXblock copies, XXXXXXXXXXtotal copies, 32767 mallocs.
0.873227s CPU time used
The list is sorted.
SORT SET COMPLETE
FA2020 COP3502 Programming Assignment 3.pdf
Programming Assignment 3
COP3502 Computer Science I – Fall 2020
Overview
This assignment is intended to make you implement several different sorting algorithms, and the means to analyze their
performance. This assignment is in two parts: a program, and an analysis.
Details
You’ve been given a scattered list of small monsters present in the Knightrola region. You need to evaluate six means of
comparison-based sort to get these monsters in order.
You need to implement six sorts for the monster structure:
• Bu
le sort
• Selection sort
• Insertion sort
• Quick sort
• Merge sort
• Merge sort, switching to insertion sort at ? ≤ 25
Data Structures and Prototypes
We’ve given you two template C files that will help you with implementation.
• integer-sorts-template.c: Contains implementation code for bu
le, selection, and quick sorts against integer
a
ays. IMPLEMENT MERGE SORT AND INSERTION SORT HERE FIRST, AND GET THEM WORKING, TO DEVELOP
YOUR UNDERSTANDING OF THE ALGORITHMS.
• monster-sorts-template.c: Contains the shell for sorting monsters via all six sorts. You may use your code from
integer-sorts-template.c directly, modifying it as necessary to work on the more complex data structures. Don’t
change the structures, the function headers, or any of the helper functions.
So your order of operations should look like this:
•
assignment-ybwsojtd.zip
Answered Same Day Nov 06, 2021

Solution

Ria answered on Nov 09 2021
149 Votes
monster-sorts-template.c
all-monster-sorts.c - Sort monsters by name and weight.
* The idea of sorting is simple: take unordered objects, and a
ange them in an
order. It has a lot of uses, so there's been a lot of work done with it. Here,
we're going to demonstrate a few of the simpler, more classic sorting techniques.
*
#include #include #include #include #include #include #pragma warning (disable: 4996)
/* Monster structure and helper functions - DO NOT MODIFY THESE. *
typedef struct monster {
int id;
char name[64];
char element[64];
int population;
double weight;
} monster;
monster* make_some_monsters(int n)
{
monster* monsters = malloc(sizeof(monster) * n);
time_t t;
srand((unsigned)time(&t));
for (int i = 0; i < n; i++)
{
monsters[i].id = i;
sprintf(monsters[i].name, "Monster #%d", rand());
sprintf(monsters[i].element, "Element #%d", rand());
monsters[i].population = rand();
monsters[i].weight = 500.0 * ((double)rand() / (double)RAND_MAX);
}
return monsters;
}
void output_monster_list(monster* list, int n, char* title) {
printf("List %s:\n", title);
for (int i = 0; i < n; i++) {
printf(" Monster %d: %s %s %d %lf\n", i, list[i].name, list[i].element, list[i].population, list[i].weight);
}
printf("\n");
}
void print_clocks(clock_t clocks) {
printf(" %lfs CPU time used\n", ((double)clocks) / CLOCKS_PER_SEC);
}
void swap_monsters(monster* list, int i, int j)
{
monster temp;
memmove(&temp, list + i, sizeof(monster));
memmove(list + i, list + j, sizeof(monster));
memmove(list + j, &temp, sizeof(monster));
}
void check_monster_sort(monster* list, int n, int use_name, int use_weight)
{
for (int i = 1; i < n; i++) {
if (compare_monsters(list + i - 1, list + i, use_name, use_weight) > 0) {
printf("*** The list is NOT sorted.\n\n");
return;
}
}
printf("The list is sorted.\n\n");
}
* The core comparison function. *
int compare_monsters(monster* m1, monster* m2, int use_name, int use_weight)
{

YOUR CODE GOES HERE.
if (use_name)
{
if (m1->name < m2->name)
{
return 0;
}
}
if (use_weight)
{
if (m1->weight < m2->weight)
{
return 0;
}
}
return 0;
}
* Implement ascending quick sort. *
int repartition(monster* list, int low_index, int high_index, int* comparisons, int* swaps,
int use_name, int use_weight)
{

YOUR CODE GOES HERE.
char* pivot_char = list[high_index].name;
int pivot_value = list[high_index].weight;
int i = low_index;
for (int j = low_index; j < high_index; j++)
{
if (use_name)
{
(*comparisons)++;
if (list[j].name < pivot_value)
{
(*swaps)++;
swap_monsters(list, i, j);
i++;
}
}
if (use_weight)
{
(*comparisons)++;
if (list[j].weight < pivot_value)
{
(*swaps)++;
swap_monsters(list, i, j);
i++;
}
}
}
/* We've now placed everything below pivot_value in list[low_index..i-1] - and that
means we can just put our pivot value in list[i]! *
swaps++;
swap_monsters(list, i, high_index);
return i;
}
* Recursive function for quick sort. *
void quick_sort_recursive(monster* list, int low_index, int high_index, int* comparisons, int* swaps,
int use_name, int use_weight)
{

YOUR CODE GOES HERE.
int pivot_index = repartition(list, low_index, high_index, comparisons, swaps, use_name, use_weight);
if (pivot_index - 1 > low_index)
{
quick_sort_recursive(list, low_index, pivot_index - 1, comparisons, swaps, use_name, use_weight);
}
if (high_index > pivot_index + 1)
{
quick_sort_recursive(list, pivot_index + 1, high_index, comparisons, swaps, use_name, use_weight);
}
}
* Shell function for quick sort. *
void quick_sort(monster* list, int n, int use_name, int use_weight)
{
int comparisons = 0;
int swaps = 0;
clock_t start_cpu, end_cpu;
printf("Quick sort %d monsters by %s...\n", n, use_name ? "name" : "weight");
start_cpu = clock();
quick_sort_recursive(list, 0, n - 1, &comparisons, &swaps, use_name, use_weight);
end_cpu = clock();
printf("Sort complete with %d comparisons and %d swaps.\n", comparisons, swaps);
print_clocks(end_cpu - start_cpu);
}
* Implement ascending bu
le sort. *
void bu
le_sort(monster* list, int n, int use_name, int use_weight)
{
int i;
int j;
int temp;
int comparisons = 0;
int swaps = 0;
clock_t start_cpu, end_cpu;
printf("Bu
le sort %d monsters by %s...\n", n, use_name ? "name" : "weight");
start_cpu = clock();

YOUR CODE GOES HERE.
for (i = n - 1; i >= 0; i--)
{
for (j = 0; j < i; j++)
{
comparisons++;
if (use_name)
sort by name
{
if (list[j].name > list[j + 1].name)
{
swaps++;
swap_monsters(list, j, j + 1);
}
}
comparisons++;
if (use_weight)
sort by weight
{
if (list[j].weight > list[j + 1].weight)
{
swaps++;
swap_monsters(list, j, j + 1);
}
}
}
}
end_cpu = clock();
printf("Sort complete with %d comparisons and %d swaps.\n", comparisons, swaps);
print_clocks(end_cpu - start_cpu);
}
* Highest-value finder for selection sort. *
int find_highest(monster* list, int n, int* comparisons, int use_name, int use_weight)
{

YOUR CODE GOES HERE.
char* highest_char = CHAR_MIN;
double highest_val = INT_MIN;
int highest_loc = -1;
int i;
for (i = 0; i <= n; i++)
{
(*comparisons)++;
if (use_name)
{
if (list[i].name > highest_char)
{
highest_loc = i;
strcpy(highest_char, list[i].name);
}
}
(*comparisons)++;
if (use_weight)
{
if (list[i].weight > highest_val)
{
highest_loc = i;
highest_val = list[i].weight;
}
}
}
return highest_loc;
}
* Implement ascending selection sort. *
void selection_sort(monster* list, int n, int use_name, int use_weight)
{
int i;
int highest;
int comparisons = 0;
int swaps = 0;
clock_t start_cpu, end_cpu;
printf("Selection sort %d monsters by %s...\n", n, use_name ? "name" : "weight");
start_cpu = clock();

YOUR CODE GOES HERE.
for (i = n - 1; i > 0; i--)
{
highest = find_highest(list, i, &comparisons, use_name, use_weight);
if (highest != i)
{
swaps++;
swap_monsters(list, highest, i);
}
}
end_cpu = clock();
printf("Sort complete with %d comparisons and %d swaps.\n", comparisons, swaps);
print_clocks(end_cpu - start_cpu);
}
* Find position for insertion sort. *
int insertion_sort_find_position(monster* list, int low_index, int high_index, monster* k, int* comparisons, int use_name, int use_weight)
{

YOUR CODE GOES HERE.
if (use_name)
{
while (high_index >= low_index && list[high_index].name > k->name)
{
list[high_index + 1] = list[high_index];
high_index--;
(*comparisons)++;
}
}
if (use_weight)
{
while (high_index >= low_index && list[high_index].weight > k->weight)
{
list[high_index + 1] = list[high_index];
high_index--;
(*comparisons)++;
}
}
(*comparisons)++;
}
* Implement insertion sort. *
void insertion_sort_internal(monster* list, int n, int* comparisons, int* copies, int* block_copies, int use_name, int use_weight)
{

YOUR CODE GOES HERE.
for (int i = 0; i < n; i++)
{
monster* key = list + i;
int j = i - 1;
insertion_sort_find_position(list, 0, j, key, comparisons, use_name, use_weight);
(*block_copies)++;

list = key;
(*copies)++;
}
}
* Shell for insertion sort. *
void insertion_sort(monster* list, int n, int use_name, int...
SOLUTION.PDF
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here
Attach File