.gitignore

main
*.dSYM

main.c

#include <stdlib.h>
#include <stdio.h>

typedef struct Node {
    int value;
    struct Node *next;
} Node;

typedef struct List {
    Node *head;
    int count;
} List;

Node *
node_create(int value)
{
    Node *node = calloc(1, sizeof(Node));

    node->value = value;
    node->next  = NULL;

    return node;
}

List *
list_create()
{
    List *list = calloc(1, sizeof(List));

    list->head  = NULL;
    list->count = 0;

    return list;
}

Node *
list_push(List *list, int value)
{
    Node *cur  = NULL,
         *tail = NULL,
         *new = node_create(value);

    if (!list->head) {
        // No elements in the list, just make this one the head.
        list->head = new;
    } else {
        for (cur = list->head; cur != NULL; cur = cur->next) {
            tail = cur;
        }

        tail->next = new;
    }

    list->count++;

    return new;
}

void
list_free(List *list)
{
    Node *current,
         *next = list->head;

    while (next != NULL) {
        current = next;
        next    = current->next;

        free(current);
    };

    free(list);
}

int
is_odd(int i)
{
    return i % 2;
}

int
is_prime(int i)
{
    int j;
    for (j = 2; j < i; j++)
    {
        if (i % j == 0) {
            return 0;
        }
    }

    return 1;
}

List *
list_select(List *list, int (*lambda)(int))
{
    List *result = list_create();
    Node *cur    = NULL;

    for (cur = list->head; cur != NULL; cur = cur->next) {
        if (lambda(cur->value)) {
            list_push(result, cur-> value);
        }
    }
    return result;
}

List *
list_reject(List *list, int (*lambda)(int))
{
    List *result = list_create();
    Node *cur    = NULL;

    for (cur = list->head; cur != NULL; cur = cur->next) {
        if (!lambda(cur->value)) {
            list_push(result, cur-> value);
        }
    }
    return result;
}

void
list_print(List *list)
{
    int i = 0;
    Node *cur = NULL;

    printf("[ ");

    for (cur = list->head; cur != NULL; cur = cur->next) {
        printf("%d ", cur->value);
        if (++i == 20) { break; }
    }

    printf("]\n");
}

void
select_reject_test()
{
    List *list,
         *result;

    list = list_create();

    list_push(list, 1);
    list_push(list, 4);
    list_push(list, 7);
    list_push(list, 10);
    list_push(list, 11);
    list_push(list, 15);

    printf("ORIGINAL LIST: ");
    list_print(list);

    result = list_select(list, is_odd);
    printf("SELECT is_odd: ");
    list_print(result);
    list_free(result);

    result = list_select(list, is_prime);
    printf("SELECT is_prime: ");
    list_print(result);
    list_free(result);

    result = list_reject(list, is_odd);
    printf("REJECT is_odd: ");
    list_print(result);
    list_free(result);

    list_free(list);
}

Node *
node_swap_with_next(Node *node) {
    Node *temp;

    temp       = node->next;
    node->next = temp->next;
    temp->next = node;

    return temp;
}

List *
list_bubble_sort(List *list)
{
    int  i;
    Node *cur;

    if (list->count < 2) {
        return list;
    }

    for (i = 0; i < list->count; i++) {
        if (list->head->value > list->head->next->value) {
            list->head = node_swap_with_next(list->head);
        }

        for (cur = list->head; cur->next->next != NULL; cur = cur->next) {
            if (cur->next->value > cur->next->next->value) {
                cur->next = node_swap_with_next(cur->next);
            }
        }
    }

    return list;
}

void
bubble_sort_test()
{
    List *list;

    list = list_create();

    list_push(list, 7);
    list_push(list, 3);
    list_push(list, 5);
    list_push(list, 2);
    list_push(list, 1);
    list_push(list, 4);

    printf("ORIGINAL LIST: ");
    list_print(list);

    list_bubble_sort(list);

    printf("SORTED LIST: ");
    list_print(list);

    free(list);
}

int
list_shift(List *list)
{
    int result;

    if (list->head == NULL) {
        printf("ERROR: shifted empty list");
        exit(1);
    }

    result     = list->head->value;
    list->head = list->head->next;
    list->count--;

    return result;
}

List *
list_merge(List *list1, List *list2)
{
    List *result;

    result = list_create();

    while (list1->head != NULL || list2->head != NULL) {
        if (list1->head == NULL) {
            list_push(result, list_shift(list2));
        }
        else if (list2->head == NULL) {
            list_push(result, list_shift(list1));
        }
        else if (list1->head->value < list2->head->value) {
            list_push(result, list_shift(list1));
        }
        else {
            list_push(result, list_shift(list2));
        }
    }

    return result;
}

List *
list_merge_sort(List *list)
{
    List *left,
         *right;
    Node *cur;

    int  i, middle;

    if (list->count < 2) {
        return list;
    }

    cur    = list->head;
    middle = list->count / 2;
    left   = list_create();
    right  = list_create();

    for (i = 0; i < middle; i++) {
        list_push(left, cur->value);
        cur = cur->next; 
    }

    for (i = middle; i < list->count; i++) {
        list_push(right, cur->value);
        cur = cur->next;
    }

    left  = list_merge_sort(left);
    right = list_merge_sort(right);

    return list_merge(left, right);
}

void
merge_sort_test()
{
    List *list,
         *result;

    list = list_create();

    list_push(list, 7);
    list_push(list, 3);
    list_push(list, 5);
    list_push(list, 2);
    list_push(list, 1);
    list_push(list, 4);

    printf("ORIGINAL LIST: ");
    list_print(list);

    result = list_merge_sort(list);

    printf("SORTED LIST: ");
    list_print(result);

    free(list);
}

int
main()
{
    /* select_reject_test(); */
    /* bubble_sort_test(); */
    merge_sort_test();

    return 0;
}

Makefile

CFLAGS=-g -Wall -Wextra

all: main

clean:
	rm -rf main *.dSYM