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?
#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; } 
