views:

1870

answers:

6

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!

+5  A: 

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.)

BoltBait
Make sure you also have http://www.cs.princeton.edu/~rs/ bookmarked -- code and errata are listed there.
Randy
Thanks mate! though I'm specifically looking for a pocket, printable reference card.
Nano Taboada
A: 

Try the Bible:

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

Tim
I don't think that's portable or a reference card. TAoP is a tome.
Thomas Owens
A "cheat sheet" for a subject like sorting is a bit silly. TAoCP vol 3 may be big, but it can be carried. He can make his own "cheat sheet" after doing some reading.
Tim
True enough. I didn't downvote you, but that is some intense reading. I looked at TAoP before, and it's no bedtime reading.
Thomas Owens
Thank you buddy but I'm looking for a printable reference card!
Nano Taboada
+6  A: 

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!

hmemcpy
I'm looking for a printable reference card, thanks anyway!
Nano Taboada
The above link is dead. The site has obviously moved to: http://www.sorting-algorithms.com/
Peterino
@Peterino Thanks! I fixed the link!
hmemcpy
+3  A: 

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.

Jonathan Leffler
Contact me at Gmail (with a dot between my names) for a transcription of the awk code -- 360 lines (too big for SO; trivial by email).
Jonathan Leffler
+13  A: 

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;
    }
}
ephemient
Thanks a lot! I'd definitely print that out!
Nano Taboada
Heck, it's carved in stone here... Thanks!
spoulson
A: 

I saw this in another post:

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

Eli
Yeah, this one. :)
spoulson
Hahaha - that's funny. I remembered it from reading this post before, searched for it in another window, and pasted it in without realizing it was the same question. I guess I'll just vote that one up then =o)
Eli
Voted one up for unfair downvoting. (Yes, I know this post has been a while.)
Xavier Ho
The above link is dead. New location of the site: http://www.sorting-algorithms.com/
Peterino