Bubble Sort

bubble_sort.c

// Bubble Sort
// http://en.wikipedia.org/wiki/Bubble_sort
// Christopher Davis 2013
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

void swap(int *array, const unsigned int from, const unsigned int to)
{
    int tmp;

    assert(NULL != array);

    tmp = array[to];
    array[to] = array[from];
    array[from] = tmp;
}

// normal, loop through every position continuously shifting bigger numbers
// up until nothing is left to sort.
void bubble_sort(int *to_sort, const unsigned int len)
{
    unsigned int i;
    unsigned short swapped = 0;

    assert(NULL != to_sort);

    do {
        swapped = 0;

        for (i = 1; i < len - 1; ++i) {
            // if the previous number is bigger than the current, swap their
            // positions, and remember that we did the swap
            if (to_sort[i-1] > to_sort[i]) {
                swap(to_sort, i-1, i);
                swapped = 1;
            }
        }
    } while (swapped);
}

// optimized, we know that all indices after the last swapped pair are
// already sorted. So reduce the "length" of the for loop to the position of
// the last swapped pair.
void opt_bubble_sort(int *to_sort, unsigned int len)
{
    unsigned int i, limit;

    assert(NULL != to_sort);

    do {
        limit = 0;

        // len -1 in the second part of the for clause causes things to get
        // skipped here. Psuedocode on Wikipedia is wrong?
        for (i = 1; i <= len-1; i++) {
            if (to_sort[i-1] > to_sort[i]) {
                swap(to_sort, i-1, i);
                limit = i;
            }
        }

        len = limit;
    } while (len);
}

int main(int argc, char *argv[])
{
    int arr[argc-1], i = 0;

    for (i = 1; i < argc; ++i) {
        arr[i-1] = atoi(argv[i]);
        printf("%d\n", arr[i-1]);
    }

    opt_bubble_sort(arr, argc);

    printf("Sorted\n");
    for (i = 0; i < argc - 1; ++i) {
        printf("%d\n", arr[i]);
    }

    return 0;
}