7
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ the selection function seems to be sorting descending is that what you want? \$\endgroup\$ – user3629249 Aug 15 '15 at 14:30
  • \$\begingroup\$ @user3629249 The point of comments should be to improve the question (e.g. seeking clarification from the author). I see a lot of irrelevant and unsubstantiated comments from you, which I am deleting. If you have suggestions for improvements (no matter how trivial), please write an answer. \$\endgroup\$ – 200_success Aug 16 '15 at 6:27
  • \$\begingroup\$ The selection sort worked fine when I tested it \$\endgroup\$ – blainarmstrong Aug 16 '15 at 23:43
4
\$\begingroup\$

Permutations

You are attempting to generate every permutation of the array, but you aren't actually doing that. You are only generating \$n^2\$ permutations instead of \$n!\$ permutations. You could use something like Heap's algorithm if you really wanted to generate every permutation (but be careful, it could make your program run a very long time).

Probably better would be to generate random permutations rather than all permutations, to keep the runtime reasonable.

const keyword

As I was reading through your code I noticed that your sorting functions make a copy of the array passed in so that you don't modify the original. Your functions should mark unmodified arguments with const. It doesn't change your program behavior but it's a good habit to develop.

\$\endgroup\$
  • \$\begingroup\$ Thanks! For some reason I thought I was getting all the permutations. Random output was what I was originally going for, but I'm doing this more as an intellectual exercise than anything else, and getting all permutations was the goal I'd set. As for marking unmodified arguments with const, I didn't realize this was possible. Again, I'm new to C, but I'm glad you told me. Thanks! \$\endgroup\$ – blainarmstrong Aug 16 '15 at 4:58
2
\$\begingroup\$

There are some things that you can do to improve the program. (As in general, they are extensions of it):

  1. Also save time. Right now, you are saving only the number of steps But different algorithms would take take different time to execute one block of code. While this is generally not most critical issue in improving performance, it should help you gain deeper understanding of underlying operations.

  2. Argue about results before seeing them. I am talking about best cases and worst cases. Think on which all inputs your algorithm should return fastest result and for which inputs it should be slow. And then check actual output. This is very useful exercise and in general, while choosing between different algorithms, play an important role.

  3. Your input at this point consists of distinct values. What if some of values are not distinct? Would it change analysis? Try to experiment with different fraction of unique values and get which algorithms are important.

All of the improvements I suggest will help you gain better understanding of complexity theory. The actual code purpose here should be only to provide an empirical evidence of your hypothesis.

**

[TO MODS: I am not sure whether this is sufficient answer, or I need to provide actual code critique. I answered the intent behind question. IF it is not adequate, let me know, I will update the answer accordingly. ]

\$\endgroup\$
  • \$\begingroup\$ These are all really interesting points. I'm now considering going back and rewriting the code to allow me to take user-defined sets of data and outputting the different results. It would serve a second purpose in practicing opening and reading files, and how to deal with files that aren't formatted the way I want them. Thanks! \$\endgroup\$ – blainarmstrong Aug 16 '15 at 23:41
2
\$\begingroup\$

There are a number of metrics you can use to track how "expensive" a sorting algorithm is. You may want to use any of (or a sum of) any of the following, depending on how this sorting algorithm will be used (is this operating on a small dataset on one computer, or terabytes of data fragmented across multiple computers, requiring some map-reduce technique to sort the data, are you sorting data on a chip that needs to have a service life of 40 years and shouldn't wear out prematurely, what are the characteristics of your hardware). You could take the same code that runs on your computer and have it sort data over a network connection or data on a hard drive (let's say you have enough data that it can't all fit in RAM at one time) and notice drastically different performance. Is your computer CPU-bound, memory-bound, I/O-bound?

  • Number of reads
  • Number of writes (minimize this if writes are expensive. cycle sort and selection sort are good)
  • Number of element swaps
  • Elapsed time (CPU time, wall time, etc)
  • Fraction of adjacent-memory reads or writes that occur within the size of your memory's cache, (to increase cache hits)
  • Amount of memory used (space complexity)

As JS1 said, you aren't generating all permutations. If you want to write your own permutation algorithm, the itertools.permutations Python recipe should be helpful (pretty similar to Heap's algorithm). Be careful, though, itertools.permutations([0,1,2,3,4,5,6]) has 5040 permutations, and itertools.permutations([0,1,...,10]) has 40 million permutations. The test cases I've usually seen are ascending sorted, descending sorted, mostly sorted, and unsorted.

I'd be interested to find out how the algorithms compare with mostly sorted lists. Here's a few ways I'd measure how approximately sorted a list is:

  • The percentage of element pairs that are in correct order
  • The percentage of adjacent element pairs that are in correct order
  • The number of elements that are in their final (sorted) position
  • The sum of the absolute value of the distance between each element's initial position and its final (sorted) position (another interesting metric here would be the standard deviation of the distance between each element's initial and final position.)

Let's consider an interesting case: The list [7, 0, 1, 2, 3, 4, 5, 6] is approximately sorted, depending on how you define "approximately sorted". Bubble sort does quite well with this one, requiring one pass to move the 7 to the end and one final pass to make sure all elements are sorted. Compare this to insertion sort or selection sort operating on the same list. Horrible performance.

If you're writing code that needs to have good parallel performance (such as on a GPU with OpenCL or CUDA), you may find some algorithms work better than others.

Let us know what you find out.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the suggestions. A lot of this is way over my head right now, but I'll probably revisit this once I have a better handle on things. \$\endgroup\$ – blainarmstrong Aug 16 '15 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.