<br />
<b>Warning</b>:  Declaration of action_plugin_subjectindex_indexer::register(&$controller) should be compatible with DokuWiki_Action_Plugin::register(Doku_Event_Handler $controller) in <b>/data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/subjectindex/action/indexer.php</b> on line <b>15</b><br />
<br />
<b>Warning</b>:  Declaration of action_plugin_mathjax_enable::register(Doku_Event_Handler &$controller) should be compatible with DokuWiki_Action_Plugin::register(Doku_Event_Handler $controller) in <b>/data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/mathjax/action/enable.php</b> on line <b>62</b><br />
<br />
<b>Warning</b>:  Declaration of action_plugin_googleanalytics::register(&$controller) should be compatible with DokuWiki_Action_Plugin::register(Doku_Event_Handler $controller) in <b>/data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/googleanalytics/action.php</b> on line <b>40</b><br />
<br />
<b>Warning</b>:  Declaration of action_plugin_folded::register(&$controller) should be compatible with DokuWiki_Action_Plugin::register(Doku_Event_Handler $controller) in <b>/data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/folded/action.php</b> on line <b>40</b><br />
<br />
<b>Warning</b>:  Declaration of action_plugin_hidden::register(&$controller) should be compatible with DokuWiki_Action_Plugin::register(Doku_Event_Handler $controller) in <b>/data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/hidden/action.php</b> on line <b>28</b><br />
<br />
<b>Warning</b>:  Declaration of action_plugin_include::register(&$controller) should be compatible with DokuWiki_Action_Plugin::register(Doku_Event_Handler $controller) in <b>/data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/include/action.php</b> on line <b>354</b><br />
<br />
<b>Warning</b>:  Declaration of action_plugin_tag::register(&$contr) should be compatible with DokuWiki_Action_Plugin::register(Doku_Event_Handler $controller) in <b>/data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/tag/action.php</b> on line <b>175</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/subjectindex/action/indexer.php:15) in <b>/data/web/virtuals/28604/virtual/www/subdom/bo/inc/auth.php</b> on line <b>532</b><br />
<br />
<b>Warning</b>:  preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in <b>/data/web/virtuals/28604/virtual/www/subdom/bo/inc/auth.php</b> on line <b>818</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/subjectindex/action/indexer.php:15) in <b>/data/web/virtuals/28604/virtual/www/subdom/bo/inc/actions.php</b> on line <b>656</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/subjectindex/action/indexer.php:15) in <b>/data/web/virtuals/28604/virtual/www/subdom/bo/inc/actions.php</b> on line <b>656</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/web/virtuals/28604/virtual/www/subdom/bo/lib/plugins/subjectindex/action/indexer.php:15) in <b>/data/web/virtuals/28604/virtual/www/subdom/bo/inc/actions.php</b> on line <b>656</b><br />

======Exercise 33: Linked List Algorithms======

   I'm going to cover two algorithms you can do on a linked list that
   involve sorting. I'm going to warn you first that if you need to sort
   the data, then don't use a linked list. These are horrible for sorting
   things, and there's much better data structures you can use if that's a
   requirement. I'm covering these two algorithms because they are
   slightly difficult to pull off with a linked list and get you thinking
   about manipulating them efficiently.

   In the interest of writing this book, I'm going to put the algorithms
   in two different files list_algos.h and list_algos.c then write a test
   in list_algos_test.c. For now just follow my structure, as it does keep
   things clean, but if you ever work on other libraries remember this
   isn't a common structure.

   In this exercise I'm going to also give you an extra challenge and I
   want you to try not to cheat. I'm going to give you the unit test
   first, and I want you to type it in. Then I want you to try and
   implement the two algorithms based on their descriptions in Wikipedia
   before seeing if your code is like my code.

======Bubble And Merge Sort======

   You know what's awesome about the Internet? I can just link you to the
   Bubble Sort page Merge Sort page and tell you to read that. Man, that
   saves me a boat load of typing. Now I can tell you how to actually
   implement each of these using the pseudo-code they have there. Here's
   how you can tackle an algorithm like this:
     * Read the description and look at any visualizations it has.
     * Either draw the algorithm on paper using boxes and lines, or
       actually take a deck of numbered cards (like Poker Cards) and try
       to do the algorithm manually. This gives you a concrete
       demonstration of how the algorithm works.
     * Create the skeleton functions in your list_algos.c file and make a
       working list_algos.h file, then setup your test harness.
     * Write your first failing test and get everything to compile.
     * Go back to the Wikipedia page and copy-paste the pseudo-code (not
       the C code!) into the guts of the first function you're making.
     * Translate this pseudo-code into good C code like I've taught you,
       using your unit test to make sure it's working.
     * Fill out some more tests for edge cases like, empty lists, already
       sorted lists, etc.
     * Repeat for the next algorithm and test.

   I just gave you the secret to figuring out most of the algorithms out
   there, that is until you get to some of the more insane ones. In this
   case you're just doing the Bubble and Merge Sorts from Wikipedia, but
   those will be good starters.

======The Unit Test======

   Here is the unit test you should try to get passing:
#include "minunit.h"
#include <lcthw/list_algos.h>
#include <assert.h>
#include <string.h>

char *values[] = {"XXXX", "1234", "abcd", "xjvef", "NDSS"};
#define NUM_VALUES 5

======List *create_words()======
{
    int i = 0;
    List *words = List_create();

    for(i = 0; i < NUM_VALUES; i++) {
        List_push(words, values[i]);
    }

    return words;
}

int is_sorted(List *words)
{
    LIST_FOREACH(words, first, next, cur) {
        if(cur->next && strcmp(cur->value, cur->next->value) > 0) {
            debug("%s %s", (char *)cur->value, (char *)cur->next->value);
            return 0;
        }
    }

    return 1;
}

char *test_bubble_sort()
{
    List *words = create_words();

    // should work on a list that needs sorting
    int rc = List_bubble_sort(words, (List_compare)strcmp);
    mu_assert(rc == 0, "Bubble sort failed.");
    mu_assert(is_sorted(words), "Words are not sorted after bubble sort.");

    // should work on an already sorted list
    rc = List_bubble_sort(words, (List_compare)strcmp);
    mu_assert(rc == 0, "Bubble sort of already sorted failed.");
    mu_assert(is_sorted(words), "Words should be sort if already bubble sorted."
);

    List_destroy(words);

    // should work on an empty list
    words = List_create(words);
    rc = List_bubble_sort(words, (List_compare)strcmp);
    mu_assert(rc == 0, "Bubble sort failed on empty list.");
    mu_assert(is_sorted(words), "Words should be sorted if empty.");

    List_destroy(words);

    return NULL;
}

char *test_merge_sort()
{
    List *words = create_words();

    // should work on a list that needs sorting
    List *res = List_merge_sort(words, (List_compare)strcmp);
    mu_assert(is_sorted(res), "Words are not sorted after merge sort.");

    List *res2 = List_merge_sort(res, (List_compare)strcmp);
    mu_assert(is_sorted(res), "Should still be sorted after merge sort.");
    List_destroy(res2);
    List_destroy(res);

    List_destroy(words);
    return NULL;
}


char *all_tests()
{
    mu_suite_start();

    mu_run_test(test_bubble_sort);
    mu_run_test(test_merge_sort);

    return NULL;
}

======RUN_TESTS(all_tests);======

   I suggest that you start with the bubble sort and get that working,
   then move on to the merge sort. What I would do is lay out the function
   prototypes and skeletons that get all three files compiling, but not
   passing the test. Then just fill in the implementation until it starts
   working.

======The Implementation======

   Are you cheating? In future exercises I will do exercises where I just
   give you a unit test and tell you to implement it, so it'll be good
   practice for you to not look at this code until you get your own
   working. Here's the code for the list_algos.c and list_algos.h:
#ifndef lcthw_List_algos_h
#define lcthw_List_algos_h

#include <lcthw/list.h>

typedef int (*List_compare)(const void *a, const void *b);

int List_bubble_sort(List *list, List_compare cmp);

======List *List_merge_sort(List *list, List_compare cmp);======

#endif

#include <lcthw/list_algos.h>
#include <lcthw/dbg.h>

inline void ListNode_swap(ListNode *a, ListNode *b)
{
    void *temp = a->value;
    a->value = b->value;
    b->value = temp;
}

int List_bubble_sort(List *list, List_compare cmp)
{
    int sorted = 1;

    if(List_count(list) <= 1) {
        return 0;  // already sorted
    }

    do {
        sorted = 1;
        LIST_FOREACH(list, first, next, cur) {
            if(cur->next) {
                if(cmp(cur->value, cur->next->value) > 0) {
                    ListNode_swap(cur, cur->next);
                    sorted = 0;
                }
            }
        }
    } while(!sorted);

    return 0;
}

inline List *List_merge(List *left, List *right, List_compare cmp)
{
    List *result = List_create();
    void *val = NULL;

    while(List_count(left) > 0 || List_count(right) > 0) {
        if(List_count(left) > 0 && List_count(right) > 0) {
            if(cmp(List_first(left), List_first(right)) <= 0) {
                val = List_shift(left);
            } else {
                val = List_shift(right);
            }

            List_push(result, val);
        } else if(List_count(left) > 0) {
            val = List_shift(left);
            List_push(result, val);
        } else if(List_count(right) > 0) {
            val = List_shift(right);
            List_push(result, val);
        }
    }

    return result;
}

======List *List_merge_sort(List *list, List_compare cmp)======
{
    if(List_count(list) <= 1) {
        return list;
    }

    List *left = List_create();
    List *right = List_create();
    int middle = List_count(list) / 2;

    LIST_FOREACH(list, first, next, cur) {
        if(middle > 0) {
            List_push(left, cur->value);
        } else {
            List_push(right, cur->value);
        }

        middle--;
    }

    List *sort_left = List_merge_sort(left, cmp);
    List *sort_right = List_merge_sort(right, cmp);

    if(sort_left != left) List_destroy(left);
    if(sort_right != right) List_destroy(right);

    return List_merge(sort_left, sort_right, cmp);
}

   The bubble sort isn't too bad to figure out, although it is really
   slow. The merge sort is much more complicated, and honestly I could
   probably spend a bit more time optimizing this code if I wanted to
   sacrifice clarity.

   There is another way to implement merge sort using a "bottom up"
   method, but it's a little harder to understand so I didn't do it. As
   I've already said, sorting algorithms on linked lists are entirely
   pointless. You could spend all day trying to make this faster and it
   will still be slower than almost any other sortable data structure. The
   nature of linked lists is such that you simply don't use them if you
   need to sort things.

======What You Should See======

   If everything works then you should get something like this:
$ make clean all
rm -rf build src/lcthw/list.o src/lcthw/list_algos.o tests/list_algos_tests test
s/list_tests
rm -f tests/tests.log
find . -name "*.gc*" -exec rm {} \;
rm -rf `find . -name "*.dSYM" -print`
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG  -fPIC   -c -o src/lcthw/list.o
 src/lcthw/list.c
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG  -fPIC   -c -o src/lcthw/list_a
lgos.o src/lcthw/list_algos.c
ar rcs build/liblcthw.a src/lcthw/list.o src/lcthw/list_algos.o
ranlib build/liblcthw.a
cc -shared -o build/liblcthw.so src/lcthw/list.o src/lcthw/list_algos.o
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG  build/liblcthw.a    tests/list
_algos_tests.c   -o tests/list_algos_tests
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG  build/liblcthw.a    tests/list
_tests.c   -o tests/list_tests
sh ./tests/runtests.sh
======Running unit tests:======
----
======RUNNING: ./tests/list_algos_tests======
======ALL TESTS PASSED======
======Tests run: 2======
tests/list_algos_tests PASS
----
======RUNNING: ./tests/list_tests======
======ALL TESTS PASSED======
======Tests run: 6======
tests/list_tests PASS
$

   After this exercise I'm not going to show you this output unless it's
   necessary to show you how it works. From now on you should know that I
   ran the tests and they all passed and everything compiled.

======How To Improve It======

   Going back to the description of the algorithms, there's several ways
   to improve these implementations, and there's a few obvious ones:
     * The merge sort does a crazy amount of copying and creating lists,
       find ways to reduce this.
     * The bubble sort Wikipedia description mentions a few optimizations,
       implement them.
     * Can you use the List_split and List_join (if you implemented them)
       to improve merge sort?
     * Go through all the defensive programming checks and improve the
       robustness of this implementation, protecting against bad NULL
       pointers, and create an optional debug level invariant that does
       what is_sorted does after a sort.

======Extra Credit======

     * Create a unit test that compares the performance of the two
       algorithms. You'll want to look at man 3 time for a basic timer
       function, and you'll want to run enough iterations to at least have
       a few seconds of samples.
     * Play with the amount of data in the lists that need to be sorted
       and see if that changes your timing.
     * Find a way to simulate filling different sized random lists and
       measuring how long they take, then graph it and see how it compares
       to the description of the algorithm.
     * Try to explain why sorting linked lists is a really bad idea.
     * Implement a List_insert_sorted that will take a given value, and
       using the List_compare, insert the element at the right position so
       that the list is always sorted. How does using this method compare
       to sorting a list after you've built it?
     * Try implementing the "bottom up" merge sort on the wikipedia page.
       The code there is already C so it should be easy to recreate, but
       try to understand how it's working compared to the slower one I
       have here.


   Copyright (C) 2010 Zed. A. Shaw

   Credits