ll_bsort.c

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

typedef struct _List {
	struct _List *next;
	int val;
} List;


List* getPre(List *dummy, List *a) {
	List *cur = dummy;
	while(cur && cur->next != a) {
		cur = cur->next;
	}
	return cur;
}

List* swap(List *head, List *a, List *b) {
	List *dummy = (List*) malloc(sizeof(List));
	dummy->next = head;
	
	List *preA = getPre(dummy, a), *nextA = a->next;
	List *preB = getPre(dummy, b), *nextB = b->next;

	// swap
	if (preB == a) {
		preA->next = b;
		b->next = a;
		a->next = nextB;
	}
	else if(preA == b) {
		preB->next = a;
		a->next = b;
		b->next = nextA;
	}
	else {
		preA->next = b;
		b->next = nextA;
		preB->next = a;
		a->next = nextB;
	}

	head = dummy->next;
	free(dummy);
	return head;
}

List *bubbleSort(List *head) {
	assert(head != NULL);
	char flag = 1;
	while(flag) {
		List *cur = head;
		flag = 0;
		while(cur && cur->next) {
			if (cur->val > cur->next->val) {
				flag = 1;
				head = swap(head, cur, cur->next);
			}
			cur = cur->next;
		}
	}
	return head;
}

void printList(List* head) {
	List *cur = head;
	while(cur) {
		printf("%d -> ", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}

List* genList(int n) {
	List *head = NULL, *cur, *prev;
	int i;
	prev = cur = head;
	for(i = 0; i < n; i++) {
		cur = (List*) malloc(sizeof(List));
		cur->val = rand() % 100;
		cur->next = NULL;
		if (head == NULL) head = cur;
		if (prev) {
			prev->next = cur;
		}
		prev = cur;
	}
	return head;
}

int main() {
	List *head;
	srand(time(NULL));
	head = genList(10);
	puts("original list");
	printList(head);
	puts("sorted list");
	head = bubbleSort(head);
	printList(head);
	return 0;
}