Return to Question

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include <cs50.h>
struct result
{
 int min;
 int max;
 unsigned long long total;
};
struct trial
{
 int length;
 struct result bubble;
 struct result insertion;
 struct result selection;
};
// prototypes
void run_trials(int start, int end, FILE *bubble, FILE *selection, FILE *insertion);
// Array functions
void swap(int arr[], int i, int j);
void fill(int arr[], int max);
void copy(int arr1[], int arr2[], int len);
// Sorting algorithms
int bubble(int arr[], int n);
int insertion(int arr[], int n);
int selection(int arr[], int n);
// Result handling
void prep_trial(struct trial *t, int i);
void prep_result(struct result *r);
void prep_file(FILE *fp);
void update_result(struct result *r, int operations);
void update_file(struct result r, int len, int count, FILE *fp);
int main(void)
{
 FILE *bub;
 FILE *sel;
 FILE *ins;
 
 // Open the file pointers
 bub = fopen("bubble.csv", "w");
 sel = fopen("selection.csv", "w");
 ins = fopen("insertion.csv", "w");
 
 // Check for errors
 if (bub == NULL
 || sel == NULL
 || ins == NULL) {
 printf("Unable to initialize one or more files. Exiting\n");
 return 1;
 }
 
 // Add the top rows of each csv file
 prep_file(bub);
 prep_file(sel);
 prep_file(ins);
 
 // This was originally supposed to be set up to run several trials
 // of different lengths with different iterators. I may still 
 // do that at some point in the future if I don't mind letting
 // the computer churn away for an hour or two
 run_trials(10, 300, bub, sel, ins);
 
 printf("All trials complete. Saving files...");
 fclose(bub);
 fclose(ins);
 fclose(sel);
 
 printf(" Done!\n");
 return 0;
}
/**
 * Set up the file's top row of headers
 */
void prep_file(FILE *fp)
{
 
 fprintf(fp, "Length,Max,Avg,Min\n");
}
/**
 * Iterate through all possible combinations of a particular arraa
 * and test the minimum, maximum, and average number of operations
 * required for each sorting algorithm
 */
void run_trials(int start, int end, FILE *bub, FILE *sel, FILE *ins)
{
 for(int i = start; i <= end; i += 10) { 
 // Set up all the necessary variables and structures
 int arr[i]; // The array to sort
 int count = 0; // The number of permutations run so far
 struct trial t; // Data for each trial
 
 // Set up the trial structure: set all three algorithms'
 // min, max, and total to 0, and set length to i
 prep_trial(&t, i); 
 
 // Fill arr with the values we need to sort
 fill(arr, i);
 
 // Run through all possible permutations of
 // the array, sorting each one and getting the
 // min, max, and average values for each run
 for (int j = 0; j < i; j++) {
 for (int k = 0; k < i - 1; k++) {
 // increment count so we know what to divide
 // each sum by to get the avg
 count++;
 
 // Swap the correct items to get the current
 // permutation
 swap(arr, k, k + 1);
 
 /**
 * Go through each algorithm and run it; the functions
 * return the number of operations performed. For each
 * one, add the current operations to avg; they will
 * then be divided by count to get the average. Then
 * compare the min and max values to see if they should
 * be updated
 */
 
 update_result(&t.bubble, bubble(arr, i));
 update_result(&t.insertion, insertion(arr, i));
 update_result(&t.selection, selection(arr, i));
 }
 }
 
 printf("Trial for array with %d elements complete\n", i);
 // Trial for length i is over; update the files
 update_file(t.bubble, i, count, bub);
 update_file(t.insertion, i, count, ins);
 update_file(t.selection, i, count, sel);
 }
}
/**
 * fill an array with values in ascending order
 */
void fill(int arr[], int max)
{
 
 for (int i = 0; i < max; i++) {
 arr[i] = i;
 }
}
/**
 * Copy the values of one array to another
 */
void copy(int source[], int dest[], int len)
{
 for(int i = 0; i < len; i++) {
 dest[i] = source[i];
 }
}
/**
 * Swap two elements in an array
 */
void swap(int arr[], int i, int j)
{
 int tmp = arr[i];
 arr[i] = arr[j];
 arr[j] = tmp;
}
/**
 * Set the length of the array used in a trial, along with 
 * the starting values of each algorithm's results
 */
void prep_trial(struct trial *t, int i)
{
 t->length = i;
 prep_result(&t->bubble);
 prep_result(&t->insertion);
 prep_result(&t->selection);
}
/**
 * Set the starting values of an algorithm's results to zero
 */
void prep_result(struct result *r)
{
 r->min = 0;
 r->max = 0;
 r->total = 0;
}
/**
 * Once a permutation of an array is sorted by an algorithm, update
 * the results where applicable
 */
void update_result(struct result *r, int operations)
{
 r->total += operations;
 if (r->min == 0
 || operations < r->min) {
 r->min = operations;
 }
 
 if (operations > r->max) {
 r->max = operations;
 }
}
/**
 * Write the results of a trial to the appropriate csv file
 */
void update_file(struct result r, int len, int count, FILE *fp)
{
 fprintf(fp, "%d,%d,%llu, %d\n", 
 len,
 r.max,
 (r.total / count),
 r.min);
}
/**
 * The bubble sort algorthim; returns the number of operations
 * performed
 */
int bubble(int a[], int n)
{
 int swapped, passes = 0, operations = 0;
 int arr[n];
 
 // Ensures that the array in the callee does not get altered
 copy(a, arr, n);
 
 // During each pass through the array, contine swapping pairs
 // of consecutive elements in the array if the one to the right
 // is less than that to the left. If no items get swapped during
 // a particular pass, terminate the loop.
 do {
 // Flag variable to check and see if anything has been
 // swapped; if not, we can stop because the array is sorted
 swapped = 0;
 
 for (int i = 1; i < n - passes; i++) {
 if(arr[i] < arr[i - 1]) {
 // arr[i] is too big; swap it out
 swap(arr, i, i - 1);
 swapped = 1;
 operations ++;
 }
 operations ++;
 }
 
 passes ++;
 }
 while (swapped);
 
 return operations;
}
/**
 * The insertion sort algorthim; returns the number of operations
 * performed
 */
int insertion(int a[], int n)
{
 int operations = 0;
 int arr[n];
 
 // Ensures that the array in the callee does not get altered
 copy(a, arr, n);
 
 // For each item in the unsorted portion of the array, 
 // pull it out, find its place in the sorted portion, and
 // shift the other items across accordingly, then place the
 // newly sorted item in the empty space created
 for(int i = 1; i < n - 1; i++) {
 int j = i, element = arr[i];
 
 while(j > 0 && arr[j - 1] > element) {
 arr[j] = arr[j - 1];
 j--;
 operations ++;
 }
 
 arr[j] = element;
 operations++;
 }
 
 return operations;
}
/**
 * The selection sort algorthim; returns the number of operations
 * performed
 */
int selection(int a[], int n)
{
 int operations = 0;
 int arr[n];
 
 // Ensures that the array in the callee does not get altered
 copy(a, arr, n);
 
 // During each pass through the unsorted portion of the array,
 // find the minimum value and append it to the sorted portion
 for(int i = 0; i < n - 1; i++) {
 int min = i;
 for (int j = i + 1; j < n; j++) {
 if (arr[j] < arr[min]) {
 min = j;
 }
 operations ++;
 }
 
 if (min != i) {
 swap(arr, min, i);
 operations ++;
 }
 }
 
 return operations;
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include <cs50.h>
struct result
{
 int min;
 int max;
 unsigned long long total;
};
struct trial
{
 int length;
 struct result bubble;
 struct result insertion;
 struct result selection;
};
// prototypes
void run_trials(int start, int end, FILE *bubble, FILE *selection, FILE *insertion);
// Array functions
void swap(int arr[], int i, int j);
void fill(int arr[], int max);
void copy(int arr1[], int arr2[], int len);
// Sorting algorithms
int bubble(int arr[], int n);
int insertion(int arr[], int n);
int selection(int arr[], int n);
// Result handling
void prep_trial(struct trial *t, int i);
void prep_result(struct result *r);
void prep_file(FILE *fp);
void update_result(struct result *r, int operations);
void update_file(struct result r, int len, int count, FILE *fp);
int main(void)
{
 FILE *bub;
 FILE *sel;
 FILE *ins;
 
 // Open the file pointers
 bub = fopen("bubble.csv", "w");
 sel = fopen("selection.csv", "w");
 ins = fopen("insertion.csv", "w");
 
 // Check for errors
 if (bub == NULL
 || sel == NULL
 || ins == NULL) {
 printf("Unable to initialize one or more files. Exiting\n");
 return 1;
 }
 
 // Add the top rows of each csv file
 prep_file(bub);
 prep_file(sel);
 prep_file(ins);
 
 // This was originally supposed to be set up to run several trials
 // of different lengths with different iterators. I may still 
 // do that at some point in the future if I don't mind letting
 // the computer churn away for an hour or two
 run_trials(10, 300, bub, sel, ins);
 
 printf("All trials complete. Saving files...");
 fclose(bub);
 fclose(ins);
 fclose(sel);
 
 printf(" Done!\n");
 return 0;
}
/**
 * Set up the file's top row of headers
 */
void prep_file(FILE *fp)
{
 
 fprintf(fp, "Length,Max,Avg,Min\n");
}
/**
 * Iterate through all possible combinations of a particular arraa
 * and test the minimum, maximum, and average number of operations
 * required for each sorting algorithm
 */
void run_trials(int start, int end, FILE *bub, FILE *sel, FILE *ins)
{
 for(int i = start; i <= end; i += 10) { 
 // Set up all the necessary variables and structures
 int arr[i]; // The array to sort
 int count = 0; // The number of permutations run so far
 struct trial t; // Data for each trial
 
 // Set up the trial structure: set all three algorithms'
 // min, max, and total to 0, and set length to i
 prep_trial(&t, i); 
 
 // Fill arr with the values we need to sort
 fill(arr, i);
 
 // Run through all possible permutations of
 // the array, sorting each one and getting the
 // min, max, and average values for each run
 for (int j = 0; j < i; j++) {
 for (int k = 0; k < i - 1; k++) {
 // increment count so we know what to divide
 // each sum by to get the avg
 count++;
 
 // Swap the correct items to get the current
 // permutation
 swap(arr, k, k + 1);
 
 /**
 * Go through each algorithm and run it; the functions
 * return the number of operations performed. For each
 * one, add the current operations to avg; they will
 * then be divided by count to get the average. Then
 * compare the min and max values to see if they should
 * be updated
 */
 
 update_result(&t.bubble, bubble(arr, i));
 update_result(&t.insertion, insertion(arr, i));
 update_result(&t.selection, selection(arr, i));
 }
 }
 
 printf("Trial for array with %d elements complete\n", i);
 // Trial for length i is over; update the files
 update_file(t.bubble, i, count, bub);
 update_file(t.insertion, i, count, ins);
 update_file(t.selection, i, count, sel);
 }
}
/**
 * fill an array with values in ascending order
 */
void fill(int arr[], int max)
{
 
 for (int i = 0; i < max; i++) {
 arr[i] = i;
 }
}
/**
 * Copy the values of one array to another
 */
void copy(int source[], int dest[], int len)
{
 for(int i = 0; i < len; i++) {
 dest[i] = source[i];
 }
}
/**
 * Swap two elements in an array
 */
void swap(int arr[], int i, int j)
{
 int tmp = arr[i];
 arr[i] = arr[j];
 arr[j] = tmp;
}
/**
 * Set the length of the array used in a trial, along with 
 * the starting values of each algorithm's results
 */
void prep_trial(struct trial *t, int i)
{
 t->length = i;
 prep_result(&t->bubble);
 prep_result(&t->insertion);
 prep_result(&t->selection);
}
/**
 * Set the starting values of an algorithm's results to zero
 */
void prep_result(struct result *r)
{
 r->min = 0;
 r->max = 0;
 r->total = 0;
}
/**
 * Once a permutation of an array is sorted by an algorithm, update
 * the results where applicable
 */
void update_result(struct result *r, int operations)
{
 r->total += operations;
 if (r->min == 0
 || operations < r->min) {
 r->min = operations;
 }
 
 if (operations > r->max) {
 r->max = operations;
 }
}
/**
 * Write the results of a trial to the appropriate csv file
 */
void update_file(struct result r, int len, int count, FILE *fp)
{
 fprintf(fp, "%d,%d,%llu, %d\n", 
 len,
 r.max,
 (r.total / count),
 r.min);
}
/**
 * The bubble sort algorthim; returns the number of operations
 * performed
 */
int bubble(int a[], int n)
{
 int swapped, passes = 0, operations = 0;
 int arr[n];
 
 // Ensures that the array in the callee does not get altered
 copy(a, arr, n);
 
 // During each pass through the array, contine swapping pairs
 // of consecutive elements in the array if the one to the right
 // is less than that to the left. If no items get swapped during
 // a particular pass, terminate the loop.
 do {
 // Flag variable to check and see if anything has been
 // swapped; if not, we can stop because the array is sorted
 swapped = 0;
 
 for (int i = 1; i < n - passes; i++) {
 if(arr[i] < arr[i - 1]) {
 // arr[i] is too big; swap it out
 swap(arr, i, i - 1);
 swapped = 1;
 operations ++;
 }
 operations ++;
 }
 
 passes ++;
 }
 while (swapped);
 
 return operations;
}
/**
 * The insertion sort algorthim; returns the number of operations
 * performed
 */
int insertion(int a[], int n)
{
 int operations = 0;
 int arr[n];
 
 // Ensures that the array in the callee does not get altered
 copy(a, arr, n);
 
 // For each item in the unsorted portion of the array, 
 // pull it out, find its place in the sorted portion, and
 // shift the other items across accordingly, then place the
 // newly sorted item in the empty space created
 for(int i = 1; i < n; i++) {
 int j = i, element = arr[i];
 
 while(j > 0 && arr[j - 1] > element) {
 arr[j] = arr[j - 1];
 j--;
 operations ++;
 }
 
 arr[j] = element;
 operations++;
 }
 
 return operations;
}
/**
 * The selection sort algorthim; returns the number of operations
 * performed
 */
int selection(int a[], int n)
{
 int operations = 0;
 int arr[n];
 
 // Ensures that the array in the callee does not get altered
 copy(a, arr, n);
 
 // During each pass through the unsorted portion of the array,
 // find the minimum value and append it to the sorted portion
 for(int i = 0; i < n - 1; i++) {
 int min = i;
 for (int j = i + 1; j < n; j++) {
 if (arr[j] < arr[min]) {
 min = j;
 }
 operations ++;
 }
 
 if (min != i) {
 swap(arr, min, i);
 operations ++;
 }
 }
 
 return operations;
}

This is my first post here on Code Review. I'm currently taking Harvard's CS50 course via EdEx.org, and we're learning about sorting algorithms. More specifically, we're studying bubble, insertion, selection, and merge sorts.

Just for kicks and giggles, I went ahead and decided to write a program that compares all three. Basically, what it does is takes arrays of varying lengths, fills them with ascending values, then runs through every possible permutation of that array and has the different algorithms sort it. It then outputs the minimum, maximum, and average number of operations used for each algorithm in a csv file so I can analyze them and make charts and whatnot.

Here's my code:

The main question I want to ask is this: Am I going about counting the number of operations required in each algorithm correctly? That said, as I am new to C programming@--though not programming in general--if you see any glaring errors in my code, I would be grateful to hear about them.

Thanks in advance for your help!

I'm currently taking Harvard's CS50 course via EdEx.org, and we're learning about sorting algorithms. More specifically, we're studying bubble, insertion, selection, and merge sorts.

Just for kicks and giggles, I went ahead and decided to write a program that compares all three. Basically, what it does is takes arrays of varying lengths, fills them with ascending values, then runs through every possible permutation of that array and has the different algorithms sort it. It then outputs the minimum, maximum, and average number of operations used for each algorithm in a .csv file so I can analyze them and make charts and whatnot.

Am I going about counting the number of operations required in each algorithm correctly?

Here's a pastebin link to my code: http://pastebin.com/bddduUi0

Here's my code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include <cs50.h>
struct result
{
 int min;
 int max;
 unsigned long long total;
};
struct trial
{
 int length;
 struct result bubble;
 struct result insertion;
 struct result selection;
};
// prototypes
void run_trials(int start, int end, FILE *bubble, FILE *selection, FILE *insertion);
// Array functions
void swap(int arr[], int i, int j);
void fill(int arr[], int max);
void copy(int arr1[], int arr2[], int len);
// Sorting algorithms
int bubble(int arr[], int n);
int insertion(int arr[], int n);
int selection(int arr[], int n);
// Result handling
void prep_trial(struct trial *t, int i);
void prep_result(struct result *r);
void prep_file(FILE *fp);
void update_result(struct result *r, int operations);
void update_file(struct result r, int len, int count, FILE *fp);
int main(void)
{
 FILE *bub;
 FILE *sel;
 FILE *ins;
 
 // Open the file pointers
 bub = fopen("bubble.csv", "w");
 sel = fopen("selection.csv", "w");
 ins = fopen("insertion.csv", "w");
 
 // Check for errors
 if (bub == NULL
 || sel == NULL
 || ins == NULL) {
 printf("Unable to initialize one or more files. Exiting\n");
 return 1;
 }
 
 // Add the top rows of each csv file
 prep_file(bub);
 prep_file(sel);
 prep_file(ins);
 
 // This was originally supposed to be set up to run several trials
 // of different lengths with different iterators. I may still 
 // do that at some point in the future if I don't mind letting
 // the computer churn away for an hour or two
 run_trials(10, 300, bub, sel, ins);
 
 printf("All trials complete. Saving files...");
 fclose(bub);
 fclose(ins);
 fclose(sel);
 
 printf(" Done!\n");
 return 0;
}
/**
 * Set up the file's top row of headers
 */
void prep_file(FILE *fp)
{
 
 fprintf(fp, "Length,Max,Avg,Min\n");
}
/**
 * Iterate through all possible combinations of a particular arraa
 * and test the minimum, maximum, and average number of operations
 * required for each sorting algorithm
 */
void run_trials(int start, int end, FILE *bub, FILE *sel, FILE *ins)
{
 for(int i = start; i <= end; i += 10) { 
 // Set up all the necessary variables and structures
 int arr[i]; // The array to sort
 int count = 0; // The number of permutations run so far
 struct trial t; // Data for each trial
 
 // Set up the trial structure: set all three algorithms'
 // min, max, and total to 0, and set length to i
 prep_trial(&t, i); 
 
 // Fill arr with the values we need to sort
 fill(arr, i);
 
 // Run through all possible permutations of
 // the array, sorting each one and getting the
 // min, max, and average values for each run
 for (int j = 0; j < i; j++) {
 for (int k = 0; k < i - 1; k++) {
 // increment count so we know what to divide
 // each sum by to get the avg
 count++;
 
 // Swap the correct items to get the current
 // permutation
 swap(arr, k, k + 1);
 
 /**
 * Go through each algorithm and run it; the functions
 * return the number of operations performed. For each
 * one, add the current operations to avg; they will
 * then be divided by count to get the average. Then
 * compare the min and max values to see if they should
 * be updated
 */
 
 update_result(&t.bubble, bubble(arr, i));
 update_result(&t.insertion, insertion(arr, i));
 update_result(&t.selection, selection(arr, i));
 }
 }
 
 printf("Trial for array with %d elements complete\n", i);
 // Trial for length i is over; update the files
 update_file(t.bubble, i, count, bub);
 update_file(t.insertion, i, count, ins);
 update_file(t.selection, i, count, sel);
 }
}
/**
 * fill an array with values in ascending order
 */
void fill(int arr[], int max)
{
 
 for (int i = 0; i < max; i++) {
 arr[i] = i;
 }
}
/**
 * Copy the values of one array to another
 */
void copy(int source[], int dest[], int len)
{
 for(int i = 0; i < len; i++) {
 dest[i] = source[i];
 }
}
/**
 * Swap two elements in an array
 */
void swap(int arr[], int i, int j)
{
 int tmp = arr[i];
 arr[i] = arr[j];
 arr[j] = tmp;
}
/**
 * Set the length of the array used in a trial, along with 
 * the starting values of each algorithm's results
 */
void prep_trial(struct trial *t, int i)
{
 t->length = i;
 prep_result(&t->bubble);
 prep_result(&t->insertion);
 prep_result(&t->selection);
}
/**
 * Set the starting values of an algorithm's results to zero
 */
void prep_result(struct result *r)
{
 r->min = 0;
 r->max = 0;
 r->total = 0;
}
/**
 * Once a permutation of an array is sorted by an algorithm, update
 * the results where applicable
 */
void update_result(struct result *r, int operations)
{
 r->total += operations;
 if (r->min == 0
 || operations < r->min) {
 r->min = operations;
 }
 
 if (operations > r->max) {
 r->max = operations;
 }
}
/**
 * Write the results of a trial to the appropriate csv file
 */
void update_file(struct result r, int len, int count, FILE *fp)
{
 fprintf(fp, "%d,%d,%llu, %d\n", 
 len,
 r.max,
 (r.total / count),
 r.min);
}
/**
 * The bubble sort algorthim; returns the number of operations
 * performed
 */
int bubble(int a[], int n)
{
 int swapped, passes = 0, operations = 0;
 int arr[n];
 
 // Ensures that the array in the callee does not get altered
 copy(a, arr, n);
 
 // During each pass through the array, contine swapping pairs
 // of consecutive elements in the array if the one to the right
 // is less than that to the left. If no items get swapped during
 // a particular pass, terminate the loop.
 do {
 // Flag variable to check and see if anything has been
 // swapped; if not, we can stop because the array is sorted
 swapped = 0;
 
 for (int i = 1; i < n - passes; i++) {
 if(arr[i] < arr[i - 1]) {
 // arr[i] is too big; swap it out
 swap(arr, i, i - 1);
 swapped = 1;
 operations ++;
 }
 operations ++;
 }
 
 passes ++;
 }
 while (swapped);
 
 return operations;
}
/**
 * The insertion sort algorthim; returns the number of operations
 * performed
 */
int insertion(int a[], int n)
{
 int operations = 0;
 int arr[n];
 
 // Ensures that the array in the callee does not get altered
 copy(a, arr, n);
 
 // For each item in the unsorted portion of the array, 
 // pull it out, find its place in the sorted portion, and
 // shift the other items across accordingly, then place the
 // newly sorted item in the empty space created
 for(int i = 1; i < n - 1; i++) {
 int j = i, element = arr[i];
 
 while(j > 0 && arr[j - 1] > element) {
 arr[j] = arr[j - 1];
 j--;
 operations ++;
 }
 
 arr[j] = element;
 operations++;
 }
 
 return operations;
}
/**
 * The selection sort algorthim; returns the number of operations
 * performed
 */
int selection(int a[], int n)
{
 int operations = 0;
 int arr[n];
 
 // Ensures that the array in the callee does not get altered
 copy(a, arr, n);
 
 // During each pass through the unsorted portion of the array,
 // find the minimum value and append it to the sorted portion
 for(int i = 0; i < n - 1; i++) {
 int min = i;
 for (int j = i + 1; j < n; j++) {
 if (arr[j] < arr[min]) {
 min = j;
 }
 operations ++;
 }
 
 if (min != i) {
 swap(arr, min, i);
 operations ++;
 }
 }
 
 return operations;
}