FUCK YEAH BUBBLE SORT


inline void swap_bytes(void *a, void *b, size_t size)
{
    char *a_char = a, *b_char = b, temp;

    while(size--) {
        temp      = *a_char;
        *a_char++ = *b_char;
        *b_char++ = temp;
    }
}

void bubble_sort(void *base, size_t num, size_t size, int (*comparator)(const void *, const void *))
{
    void *first, *second;
    size_t pass, passes = num - 1, i;
    int result;

    if(num > 1) {
        for(pass = 0; pass < passes; ++pass) {
            second = base + size * num - size;
            first  = second - size;

            for(i = num; i > pass + 1; --i) {
                result = comparator(first, second);
                if(result == 1)
                    swap_bytes(first, second, size);
                first -= size;
                second -= size;
            }
        }
    }
}

Here you go, /prog/, a generic implementation of bubble sort that can replace qsort().


/* hsort.c -- an implementation of the heap sort algorithm in C.
 * Public domain.
 */

#include <string.h>

inline static void
swap_bytes(void *a, void *b, size_t size)
{
    char *a_char = a, *b_char = b, temp;

    while(size--) {
        temp      = *a_char;
        *a_char++ = *b_char;
        *b_char++ = temp;
    }
}

// these macros make the code more readable, and a bit faster than a sift_down
// function.
#define UPDATE_CHILD    (child_ptr = base + ((root_ptr - base) * 2 + size))
#define HAS_CHILD       (UPDATE_CHILD <= end_ptr)
#define HAS_SIBLING     (child_ptr < end_ptr)
#define LESS_THAN(a, b) (cmp(a, b) < 0)
#define END             (base + end * size)
#define ROOT            (base + start * size)
#define SIBLING         (child_ptr + size)
#define SIFT_DOWN                                         \
{                                                         \
    root_ptr = ROOT;                                      \
    end_ptr  = END;                                       \
    while(HAS_CHILD) {                                    \
        if(HAS_SIBLING && LESS_THAN(child_ptr, SIBLING))  \
            child_ptr += size;                            \
        if(LESS_THAN(root_ptr, child_ptr)) {              \
            swap_bytes(root_ptr, child_ptr, size);        \
            root_ptr = child_ptr;                         \
        }                                                 \
        else break;                                       \
    }                                                     \
}

void
hsort(void *base, size_t num, size_t size, int (*cmp)(const void*, const void*))
{
    size_t end = num - 1;
    void *root_ptr, *child_ptr, *end_ptr; // used by SIFT_DOWN only.
    int start = end / 2;

    if(base && num && size && cmp) {
        // arrange the array into a heap.
        while(start >= 0) {
            SIFT_DOWN;
            start--;
        }
        start = 0;

        while(end) {
            // swap the root of the heap with the last item.
            // also decrease heap size (end) to keep previously placed values.
            swap_bytes(base + end-- * size, base, size);
            // put the next largest element at the top of the heap.
            SIFT_DOWN;
        }
    }
}

Currently about half as fast as qsort() on my system; this sorts 1,048,576 random ints in about 0.36 seconds, qsort() in about 0.18 seconds.

>>8
slow but steady.

qsort() if based on quicksort has that very slight chance of getting into a degenerate case and being no quicker than bubblesort.

>>9
I thought that qsort() was always based on quicksort. It's kinda implied in the name.

Introsort is probably the best choice if you want speed with a worst-case efficiency of O(n log n).