3
\$\begingroup\$

Your function must have an input that takes in an array containing 10000 random names, and must sort these names in alphabetical order. Names have a random length of up to 128 characters. ISO/IEC 8859-1 character set assumed to be used for the list of names.

Usable list of names can be found at http://www.opensourcecf.com/1/2009/05/10000-Random-Names-Database.cfm (firstNameFirst column).

You may not use any native sorting functions available to your language.

The winner will be based purely on speed.

Language used must be compilable/runnable on a standard *nix box.

\$\endgroup\$
  • \$\begingroup\$ So, simply sort a list of lines by byte values? Or do we need to account for space between names or encodings? \$\endgroup\$ – Joey Adams Apr 19 '11 at 18:09
  • \$\begingroup\$ @Joey Adams simply sort a list by byte values. \$\endgroup\$ – dqhendricks Apr 19 '11 at 18:15
  • \$\begingroup\$ 10000x128 isn't very much data. LC_ALL=C sort randomNames.csv takes about 20 milliseconds on my system. Any faster, and it would be nearly indistinguishable from cat. \$\endgroup\$ – Joey Adams Apr 19 '11 at 18:39
  • \$\begingroup\$ @Joey Adams, was planning on running each function 100x for testing. \$\endgroup\$ – dqhendricks Apr 19 '11 at 19:06
  • \$\begingroup\$ If anyone's interested in testing large inputs, here is a program that generates 1,000,000 lines (each no longer than 128 characters including newline) of ISO 8859-1 text. \$\endgroup\$ – Joey Adams Apr 19 '11 at 20:10
0
\$\begingroup\$

C - B-tree sort

This sorts randomNames.csv in about 5.8ms on my Core 2 T5500 @ 1.66GHz. My testing utility is here.

It isn't the fastest algorithm for sorting this quantity of data, but I didn't feel like trieing.

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Btree Btree;

static void btree_insert(Btree **btree, const char *key);
static void btree_emit_and_free(Btree *btree, const char ***out);

void sort(const char **strings, size_t count, const char **out)
{
    size_t i;
    Btree *tree = NULL;
    const char **out_start = out;

    for (i = 0; i < count; i++)
        btree_insert(&tree, strings[i]);

    btree_emit_and_free(tree, &out);

    assert(out - out_start == (ssize_t) count);
}

/*
 * Maximum (U) and minimum (L) number of *keys* per B-tree node.
 *
 * The maximum number of *branches* a B-tree may have is U+1 :
 *
 *       KEY   KEY
 *     /     |     \
 * branch  branch  branch
 */
#define U 20
#define L (U / 2)

struct Btree {
    /* Number of keys (rather than branches). */
    unsigned char count;

    /* 0 if node is a leaf, 1 if it has leaf children, etc. */
    unsigned char depth;

    const char *keys[U];

    /* Allocated to U+1 items if this is an internal node. */
    Btree *branches[];
};

static Btree *allocLeaf(void)
{
    return malloc(sizeof(Btree));
}

static Btree *allocInternal(void)
{
    return malloc(sizeof(Btree) + (U+1) * sizeof(Btree *));
}

static bool insert(Btree *node, const char *x,
                   const char **new_x, Btree **new_xr);
static bool insert_item(Btree *node, unsigned int k,
                        const char  *x,     Btree  *xr,
                        const char **new_x, Btree **new_xr);
static unsigned int
find_insertion_point(const char *keys[], unsigned int count, const char *x);

static void btree_insert(Btree **btree, const char *key)
{
    if (*btree == NULL) {
        Btree *root = allocLeaf();
        root->count = 1;
        root->depth = 0;
        root->keys[0] = key;
        *btree = root;
    } else {
        const char *new_x;
        Btree *new_xr;

        if (insert(*btree, key, &new_x, &new_xr)) {
            Btree *root = allocInternal();
            root->count = 1;
            root->depth = (*btree)->depth + 1;
            root->keys[0] = new_x;
            root->branches[0] = *btree;
            root->branches[1] = new_xr;
            *btree = root;
        }
    }
}

static bool insert(Btree *node, const char *x,
                   const char **new_x, Btree **new_xr)
{
    unsigned int k = find_insertion_point(node->keys, node->count, x);
    Btree *xr;

    if (node->depth == 0)
        xr = NULL;
    else if (insert(node->branches[k], x, new_x, new_xr))
        x = *new_x, xr = *new_xr;
    else
        return false;

    return insert_item(node, k, x, xr, new_x, new_xr);
}

static bool insert_item(Btree *node, unsigned int k,
                        const char  *x,     Btree  *xr,
                        const char **new_x, Btree **new_xr)
{
    unsigned int i;
    bool internal = xr != NULL;

    if (node->count < U) {
        /* Enough case */
        for (i = node->count; i-- > k;)
            node->keys[i + 1] = node->keys[i];
        node->keys[k] = x;
        if (internal) {
            for (i = node->count + 1; i-- > k + 1;)
                node->branches[i + 1] = node->branches[i];
            node->branches[k + 1] = xr;
        }
        node->count++;
        return false;
    } else {
        Btree *r = internal ? allocInternal() : allocLeaf();

        node->count = L;
        r->count = L;
        r->depth = node->depth;

        if (k < L) {
            /* Left case */
            *new_x = node->keys[L - 1];
            for (i = 0; i < L; i++)
                r->keys[i] = node->keys[i + L];
            for (i = L - 1; i-- > k;)
                node->keys[i + 1] = node->keys[i];
            node->keys[k] = x;
            if (internal) {
                for (i = 0; i <= L; i++)
                    r->branches[i] = node->branches[i + L];
                for (i = L; i-- > k + 1;)
                    node->branches[i + 1] = node->branches[i];
                node->branches[k + 1] = xr;
            }
        } else if (k == L) {
            /* Central case */
            *new_x = x;
            for (i = 0; i < L; i++)
                r->keys[i] = node->keys[i + L];
            if (internal) {
                r->branches[0] = xr;
                for (i = 1; i <= L; i++)
                    r->branches[i] = node->branches[i + L];
            }
        } else {
            /* Right case */
            *new_x = node->keys[L];
            for (i = 0; i < k - L - 1; i++)
                r->keys[i] = node->keys[i + L + 1];
            r->keys[k - L - 1] = x;
            for (i = k - L; i < L; i++)
                r->keys[i] = node->keys[i + L];
            if (internal) {
                for (i = 0; i < k - L; i++)
                    r->branches[i] = node->branches[i + L + 1];
                r->branches[k - L] = xr;
                for (i = k - L + 1; i <= L; i++)
                    r->branches[i] = node->branches[i + L];
            }
        }

        *new_xr = r;
        return true;
    }
}

static unsigned int
find_insertion_point(const char *keys[], unsigned int count, const char *x)
{
    unsigned int start = 0;
    unsigned int middle;

    while (count) {
        middle = count >> 1;
        if (strcmp(x, keys[start + middle]) < 0) {
            count = middle;
        } else {
            start += middle + 1;
            count -= middle + 1;
        }
    }

    return start;
}

static void btree_emit_and_free(Btree *btree, const char ***out)
{
    unsigned int i;

    if (btree->depth == 0) {
        for (i = 0; i < btree->count; i++)
            *(*out)++ = btree->keys[i];
    } else {
        for (i = 0; i < btree->count; i++) {
            btree_emit_and_free(btree->branches[i], out);
            *(*out)++ = btree->keys[i];
        }
        btree_emit_and_free(btree->branches[btree->count], out);
    }

    free(btree);
}
\$\endgroup\$
  • \$\begingroup\$ BTree wins it... by default. \$\endgroup\$ – dqhendricks Apr 21 '11 at 22:22
  • \$\begingroup\$ @dqhendricks: You mean because nobody else posted an answer? I know for a fact a faster solution is possible. \$\endgroup\$ – Joey Adams Apr 22 '11 at 2:37
  • \$\begingroup\$ yeah, but no one wants to try \$\endgroup\$ – dqhendricks Apr 22 '11 at 4:13

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.