A good reference card / cheat sheet with the basic sort algorithms in C?

Question

I've been looking (without great luck) for the perfect reference card with all the basic sorting algos in C (or maybe in pseudo code). Wikipedia is a terrific source of info but this time I'm looking for something definitely more portable (pocket size if possible) and of course printable. Any suggestion would be much appreciated!

Answer 1

What you need is a book called Algorithms in C by Robert Sedgewick.

http://www.amazon.com/Algorithms-C-paperback-Robert-Sedgewick/dp/0768682339/

I would probably look for a used one. New ones are somewhat expensive (but, still totally worth it.)

Answer 2

Try the Bible:

http://dannyreviews.com/h/Art_Programming.html

Answer 3

You should definitely check out the Animated Sorting Algorithms page. It is an amazing resource for sorting algorithms.

EDIT Thanks to Peterino for the new link!

Answer 4

Generally speaking, people do not worry too much about the different algorithms, and many people use the standard library qsort() function (which might or might not actually use a Quicksort) to do their sorting. When they don't use it, they usually have more complex requirements. This might be because they need to external sorting (spilling data to disk), or for reasons related to performance. Occasionally, the perceived overhead of the function-call-per-comparison associated with using qsort() (or, indeed, bsearch()) is too great. Sometimes, people don't want to risk the potential O(N^2) worst-case behaviour of Quicksort, but most production qsort() algorithms will avoid that for you.

Quite apart from the various books on algorithms - Sedgewick is one such, but there are many others - you could also take a look at Jon Bentley's "Programming Pearls" or "More Programming Pearls" books. This would be good, anyway - they are excellent - but "More Programming Pearls" also includes a library of simple algorithms written in awk, including insertion sort, heap sort and quick sort. It misses out Bubble Sort, Shell Sort, and BogoSort. It also does not include Radix Sort.

Answer 5

I made this for a friend of mine studying C, maybe you will find it helpful:

#include <stdlib.h>
#include <string.h>

static void swap(int *a, int *b) {
    if (a != b) {
        int c = *a;
        *a = *b;
        *b = c;
    }
}

void bubblesort(int *a, int l) {
    int i, j;

    for (i = l - 2; i >= 0; i--)
        for (j = i; j < l - 1 && a[j] > a[j + 1]; j++)
            swap(a + j, a + j + 1);
}

void selectionsort(int *a, int l) {
    int i, j, k;
    for (i = 0; i < l; i++) {
        for (j = (k = i) + 1; j < l; j++)
            if (a[j] < a[k])
                k = j;
        swap(a + i, a + k);
    }
}

static void hsort_helper(int *a, int i, int l) {
    int j;

    for (j = 2 * i + 1; j < l; i = j, j = 2 * j + 1)
        if (a[i] < a[j])
            if (j + 1 < l && a[j] < a[j + 1])
                swap(a + i, a + ++j);
            else
                swap(a + i, a + j);
        else if (j + 1 < l && a[i] < a[j + 1])
            swap(a + i, a + ++j);
        else
            break;
}

void heapsort(int *a, int l) {
    int i;

    for (i = (l - 2) / 2; i >= 0; i--)
        hsort_helper(a, i, l);

    while (l-- > 0) {
        swap(a, a + l);
        hsort_helper(a, 0, l);
    }
}

static void msort_helper(int *a, int *b, int l) {
    int i, j, k, m;

    switch (l) {
        case 1:
            a[0] = b[0];
        case 0:
            return;
    }

    m = l / 2;
    msort_helper(b, a, m);
    msort_helper(b + m, a + m, l - m);
    for (i = 0, j = 0, k = m; i < l; i++)
        a[i] = b[j < m && !(k < l && b[j] > b[k]) ? j++ : k++];
}

void mergesort(int *a, int l) {
    int *b;

    if (l < 0)
        return;

    b = malloc(l * sizeof(int));
    memcpy(b, a, l * sizeof(int));
    msort_helper(a, b, l);
    free(b);
}

static int pivot(int *a, int l) {
    int i, j;

    for (i = j = 1; i < l; i++)
        if (a[i] <= a[0])
            swap(a + i, a + j++);

    swap(a, a + j - 1);

    return j;
}

void quicksort(int *a, int l) {
    int m;

    if (l <= 1)
        return;

    m = pivot(a, l);
    quicksort(a, m - 1);
    quicksort(a + m, l - m);
}

struct node {
    int value;
    struct node *left, *right;
};

void btreesort(int *a, int l) {
    int i;
    struct node *root = NULL, **ptr;

    for (i = 0; i < l; i++) {
        for (ptr = &root; *ptr;)
            ptr = a[i] < (*ptr)->value ? &(*ptr)->left : &(*ptr)->right;
        *ptr = malloc(sizeof(struct node));
        **ptr = (struct node){.value = a[i]};
    }

    for (i = 0; i < l; i++) {
        struct node *node;
        for (ptr = &root; (*ptr)->left; ptr = &(*ptr)->left);
        a[i] = (*ptr)->value;
        node = (*ptr)->right;
        free(*ptr);
        (*ptr) = node;
    }
}

Answer 6

I saw this in another post:

http://vision.bc.edu/~dmartin/teaching/sorting/anim-html/all.html