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