[C++] List sorting – bucket sort and others

In this article I will show you pure implementation of algorithms, which can be used to sort lists + list implementation. Bucket sort, quicker sort and insertion sort. Check also previous articles on the same topic:
- C++ radix sort implementation,
- C++ counting sort implementation.

#include 
#include 
#include 
const int MAX_LIST_LENGTH = 70000;
const int BUCKETS_COUNT = 1000;

typedef struct node {
        float number;
        node* next;
} node;

// list functions, head as a parameter
void init(node*&);
inline bool empty(node*); // true if empty
bool push(node*&, float); // true if pushed correctly on head
void make_list(node*&, int); // create list with random numbers
void print_all(node*); // print list

void bucket_sort(node*&); // O(n)
node* find(node*, float); // where the node should be put
void insert(node*&, node* tmp, node* place); // insert tmp after place

void quicker_sort(node*&); // O(nlogn)
void insertion_sort(node*&); // O(n^2)

int main() {
        time_t start, end;
        long dif;
        node* head;

        printf("Size of data: %d\n", MAX_LIST_LENGTH);

        printf("\nbucket_sort, O(n):\n");
        make_list(head, MAX_LIST_LENGTH);
        //print_all(head);
        start = clock();
        bucket_sort(head);
        end = clock();
        dif = end - start;
        //print_all(head);
        printf("%ld\n", dif / 1000);

        head = NULL;
        printf("\nquicker_sort, O(nlogn):\n");
        make_list(head, MAX_LIST_LENGTH);
        //print_all(head);
        start = clock();
        quicker_sort(head);
        end = clock();
        dif = end - start;
        //print_all(head);
        printf("%ld\n", dif / 1000);

        head = NULL;
        printf("\ninsertion_sort, O(n^2):\n");
        make_list(head, MAX_LIST_LENGTH);
        //print_all(head);
        start = clock();
        insertion_sort(head);
        end = clock();
        dif = end - start;
        //print_all(head);
        printf("%ld\n", dif / 1000);

        return 0;
}

// implementation

void insertion_sort(node*& head) {
        node* sorted = NULL;
        node* tmp, *place;
        while (head) {
                tmp = head;
                head = head->next;
                place = find(sorted, tmp->number);
                insert(sorted, tmp, place);
        }
        head = sorted;
}

node* find(node* head, float x) {
        node *place = NULL;
        while (!empty(head) && x > head->number) {
                place = head;
                head = head->next;
        }
        return place;
}

void insert(node*& head, node* tmp, node* place) {
        if (place == NULL) { // to head
                tmp->next = head;
                head = tmp;
        } else {
                tmp->next = place->next;
                place->next = tmp;
        }
}

void bucket_sort(node*& head) {
        node* buckets[BUCKETS_COUNT], *place, *tmp;
        for (int i = 0; i number * BUCKETS_COUNT) % BUCKETS_COUNT;
                place = find(buckets[y], head->number);
                tmp = head;
                head = head->next;
                insert(buckets[y], tmp, place);
        }
        y = 0;
        node* last;
        // join buckets
        while (y next;
                        if (empty(head))
                                head = tmp;
                        else
                                last->next = tmp;
                        last = tmp;
                        while (!empty(buckets[y])) { // go to the end of the list
                                last = buckets[y];
                                buckets[y] = buckets[y]->next;
                        }
                }
                y++;
        }
}

void quicker_sort(node*& head) {
        if (head && head->next) {
                node *smaller = NULL, *equal = NULL, *bigger = NULL;
                float key = head->number;
                node* tmp = head;
                head = head->next;
                tmp->next = equal;
                equal = tmp;
                while (head) {
                        tmp = head;
                        head = head->next;
                        if (tmp->number == key) {
                                tmp->next = equal;
                                equal = tmp;
                        } else if (tmp->number next = smaller;
                                smaller = tmp;
                        } else {
                                tmp->next = bigger;
                                bigger = tmp;
                        }
                }
                quicker_sort(smaller);
                quicker_sort(bigger);
                if (smaller) {
                        head = smaller;
                        while (smaller->next)
                                smaller = smaller->next;
                        smaller->next = equal;
                } else {
                        head = equal;
                }
                while (equal->next)
                        equal = equal->next;
                equal->next = bigger;
        }
}

void print_all(node* head) {
        while (!empty(head)) {
                printf(" %.2f", head->number);
                head = head->next;
        }
        printf("\n");
}

void make_list(node*& head, int dlugosc) {
        init(head);
        srand(time(NULL));
        for (int i = 0; i number = number;
                p->next = head;
                head = p;
                return 1;
        }
}

This code on my computer prints:

Size of data: 70000

bucket_sort, O(n):
10

quicker_sort, O(nlogn):
20

insertion_sort, O(n^2):
13370

As you see bucket sort and quicker sort are very fast compared to insertion sort. You can experiment with number of buckets and of course try to improve my implementation ;)