Answer To: 4608690_1712792546_FA2020COP3502ProgrammingAssign.pdf Programming Assignment 3 COP3502 Computer...
Ria answered on Nov 07 2021
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...