sorting linked list

// =========================================================
// 
//       Filename:  listsort.cpp
// 
//    Description:  
// 
//        Version:  1.0
//        Created:  03/09/2012 04:06:26 PM
//       Revision:  none
//       Compiler:  g++
// 
//         Author:  LI YAN (lyan), lyan@cs.ucr.edu
//        Company:  U of California Riverside
//      Copyright:  Copyright (c) 03/09/2012, LI YAN
// 
// =========================================================
//
// notes:
// 1. insert into head does not need dummy node
// 2. insert into tail needs a dummy node to make code simple, there is no tail
// node in an empty list anyway
// 3. delete from head does not need dummy node
// 4. maintain a tail pointer if you need to insert at tail
// 5. it often helps use two pointers walking the same list
// 6. be careful in off-by-one
// 7. know the primitives, insert/delete at ptr->next and at head or tail
// 8. check NULL before dereference use -> or *p

#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <utility>
using namespace std;

struct node {
    int val;
    node *next;
};

node* insertsort(node *head)
{
    if (head==NULL || head->next==NULL) return head;

    node ahead, bhead; // dummy ahead is not necessary since we only delete from head
    node *p1, *p2, *u;
    ahead.next=head; bhead.next=NULL;

    for(p1=&ahead; p1->next!=NULL; ) {
        u = p1->next; p1->next = p1->next->next;
        for(p2=&bhead; p2->next!=NULL; p2=p2->next) {
            if (u->val > p2->next->val) break;
        }
        u->next = p2->next;
        p2->next = u;
    }
    return bhead.next;
}

node* selectsort(node *head)
{
    if (head==NULL || head->next==NULL) return head;

    node dummy; dummy.next=head; // use dummy head to simplify delete from head
    node *curr, *ptr, *u, *newhead=NULL;
    int vmax;
    while(dummy.next->next != NULL) { // keep going as long as list has >=2 items
        curr=ptr=&dummy; u=ptr->next; vmax = u->val;
        for(ptr=ptr->next; ptr->next!=NULL; ptr=ptr->next) {
            u=ptr->next;
            if (u->val > vmax) { curr = ptr; vmax = u->val; }
        } 
        ptr=curr->next;
        curr->next = curr->next->next;
        ptr->next=newhead;
        newhead=ptr;
    }
    dummy.next->next = newhead;
    return dummy.next;
}

// code from this point on inspired or learned from Robert Sedgewick
node* mergesort(node *head)
{
    node dummy;
    node *left, *right, *ptr, *p1, *p2;

    if (head==NULL || head->next == NULL) return head;
    for(p1=head, p2=head->next; p2!=NULL && p2->next!=NULL; p1=p1->next, p2=p2->next->next) ;
    left=head; right=p1->next; p1->next=NULL;

    //printf("p1 %d p2 %d\n", left.next->val, right.next->val);

    p1=mergesort(left);
    p2=mergesort(right);

    dummy.next=NULL;
    for(ptr=&dummy; p1!=NULL && p2!=NULL; ) {
        if (p1->val <= p2->val) { ptr->next=p1; ptr=p1; p1=p1->next; }
        else { ptr->next=p2; ptr=p2; p2=p2->next; }
    }
    ptr->next = (p1==NULL) ? p2 : p1; // this appends remain of p1 or p2 in one stmt
    return dummy.next;
}

// quick sort with Lumoto partition
// returns (head, tail) of sorted list
pair<node*, node*>
quicksort(node *head)
{
    node dummy;
    node *low, *high;
    node *pivot, *ptr, *u, *newhead, *newtail;
    int n, k, i;

    if (head==NULL || head->next==NULL) return make_pair(head, head);

    for(n=0, ptr=head; ptr!=NULL; ptr=ptr->next, n++) ;

    k=rand()%n;
    dummy.next=head;
    for(i=0, ptr=&dummy; i<k; ++i, ptr=ptr->next) ;
    pivot=ptr->next; assert(pivot);
    ptr->next=ptr->next->next;

    low=high=NULL;
    for(ptr=&dummy; ptr->next != NULL; ) {
        u=ptr->next; ptr->next = u->next;
        if (u->val <= pivot->val) { u->next = low; low=u; }
        else { u->next = high; high=u; }
    }
    //printf("low %d high %d\n", low.next->val, high.next->val);
    pair<node*, node*> pp1, pp2;
    pp1 = quicksort(low);
    pp2 = quicksort(high);

    if (pp1.first != NULL) newhead = pp1.first;
    else newhead = pivot;

    if (pp2.second != NULL) newtail = pp2.second;
    else newtail = pivot;

    if (pp1.second != NULL) pp1.second->next = pivot;
    pivot->next = pp2.first;

    return make_pair(newhead, newtail);
}

void print(const node *head)
{
    const node *p;
    for(p=head; p; p=p->next)
        printf("%d ", p->val);
    putchar('\n');
}

int main()
{
    srand((unsigned)time(NULL));
    int a[] = {10, 3, 4, 5, 1, 9, 8};

    int n=sizeof(a)/sizeof(int);
    node v0[10], v1[10], v2[10], v3[10];
    node *head;
    for(int i=0; i<n; ++i) {
        v0[i].val = v1[i].val = v2[i].val = v3[i].val = a[i];
        if (i<n-1) { v0[i].next = &v0[i+1]; v1[i].next = &v1[i+1]; v2[i].next = &v2[i+1]; v3[i].next = &v3[i+1]; }
        else { v0[i].next = v1[i].next = v2[i].next = v3[i].next = 0; }
    }

    puts("v0[]"); print(v0);
    puts("insertion sort:");
    head=selectsort(v0);
    print(head);
    putchar('\n');

    puts("v1[]"); print(v1);
    puts("selection sort:");
    head=selectsort(v1);
    print(head);
    putchar('\n');

    puts("v2[]"); print(v2);
    puts("merge sort:");
    head=mergesort(v2);
    print(head);
    putchar('\n');

    puts("v3[]"); print(v3);
    puts("quick sort:");
    head=(quicksort(v3)).first;
    print(head);
    putchar('\n');
}