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 »
Please look at the file


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. 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 Bubble 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 Bubble sort 500 monsters by weight... Sort complete with 124750 comparisons and 60639 swaps. 0.006494s CPU time used The list is sorted. Selection sort 500 monsters by weight... Sort complete with 125249 comparisons 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 (125042 total 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 Bubble sort 500 monsters by name... Sort complete with 124750 comparisons and 62213 swaps. 0.009424s CPU time used The list is sorted. Selection sort 500 monsters by name... Sort complete with 125249 comparisons 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 (124273 total 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 Bubble sort 5000 monsters by weight... Sort complete with 12497500 comparisons and 6236050 swaps. 0.670259s CPU time used The list is sorted. Selection sort 5000 monsters by weight... Sort complete with 12502499 comparisons and 4994 swaps. 0.166510s CPU time used The list is sorted. Insertion sort 5000 monsters by weight... Sort complete with 6266440 comparisons and 4990 block copies (12503418 total 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, 123616 total 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, 130606 total copies, 255 mallocs. 0.003925s CPU time used The list is sorted. SORT SET COMPLETE SORT SET: n = 5000, all sorts, by name Bubble sort 5000 monsters by name... Sort complete with 12497500 comparisons and 6261968 swaps. 0.905517s CPU time used The list is sorted. Selection sort 5000 monsters by name... Sort complete with 12502499 comparisons and 4986 swaps. 0.415122s CPU time used The list is sorted. Insertion sort 5000 monsters by name... Sort complete with 6240521 comparisons and 4989 block copies (12500133 total 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, 123616 total 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, 130519 total 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 929307 comparisons and 439488 swaps. 0.059896s CPU time used The list is sorted. Merge sort 50000 monsters... Sort complete with 718325 comparisons, 99998 block copies, 1568928 total copies, 49999 mallocs. 0.078171s CPU time used The list is sorted. Merge-insertion sort 50000 monsters... Sort complete with 880810 comparisons, 46349 block copies, 1728155 total 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 905003 comparisons and 459121 swaps. 0.075177s CPU time used The list is sorted. Merge sort 50000 monsters... Sort complete with 717938 comparisons, 99998 block copies, 1568928 total copies, 49999 mallocs. 0.079564s CPU time used The list is sorted. Merge-insertion sort 50000 monsters... Sort complete with 881791 comparisons, 46317 block copies, 1727414 total 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 500000 monsters by weight... Sort complete with 11307984 comparisons and 5816004 swaps. 0.722573s CPU time used The list is sorted. Merge sort 500000 monsters... Sort complete with 8836731 comparisons, 999998 block copies, 18951424 total copies, 499999 mallocs. 0.933181s CPU time used The list is sorted. Merge-insertion sort 500000 monsters... Sort complete with 9615479 comparisons, 455862 block copies, 18955572 total 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 500000 monsters by name... Sort complete with 11321175 comparisons and 5597328 swaps. 0.867876s CPU time used The list is sorted. Merge sort 500000 monsters... Sort complete with 8837787 comparisons, 999998 block copies, 18951424 total copies, 499999 mallocs. 1.031811s CPU time used The list is sorted. Merge-insertion sort 500000 monsters... Sort complete with 9610466 comparisons, 456173 block copies, 18957396 total 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: • Bubble 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 bubble, selection, and quick sorts against integer arrays. 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 DayNov 06, 2021

Answer To: cop3502-as3-sample-output.txt SORT SET: n = 50, all sorts, by weight Bubble sort 50 monsters by...

Ria answered on Nov 09 2021
147 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 arrange 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 bubble sort. */
void bubble_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("Bubble 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
Have files?