#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* --- doubly linked list! --- */
/*
* head -> node_1 -> node_2 -> ... -> node_n -> NULL
*
* head is simply node with NULL previous node
*/
struct node
{
int i;
struct node *p;
struct node *n;
};
struct node *list_new_head()
{
struct node *h = (struct node *) malloc(sizeof(*h));
h->p = h->n = NULL;
return h;
}
int list_is_head(struct node *n)
{
return !(n->p);
}
struct node *list_new_node(int i)
{
struct node *n = (struct node *) malloc(sizeof(*n));
n->i = i;
return n;
}
void list_insert_after(struct node *p, struct node *n)
{
n->p = p;
n->n = p->n;
if (p->n)
p->n->p = n;
p->n = n;
}
void list_detach(struct node *n)
{
if (!list_is_head(n))
{
n->p->n = n->n;
if (n->n)
n->n->p = n->p;
}
else
printf("Tried to detach head!");
}
/* --- qsort --- */
#define list_qsort(n) list_qsort_segment(n, NULL)
/* if b is NULL, sort till list end */
void list_qsort_segment(struct node *a, struct node *b)
{
/* skip 0 or 1 length segments */
if (a == b || a->n == b)
return;
/*
* 'p' is pivot, which is the first element
* put elements less than pivot before it, greater after
*/
struct node *p = a->n, *i, *n, *e = p, *x = b ? b->n : NULL;
for (i = p->n; i != x; i = n)
{
n = i->n;
list_detach(i);
if (i->i < p->i)
list_insert_after(a, i);
else
list_insert_after(p, e == p ? (e = i) : i);
}
/* print one step */
void list_qsort_print_step(struct node *p);
list_qsort_print_step(p);
/* now sort new segments on right and left sides of pivot the same way */
list_qsort_segment(p, e);
list_qsort_segment(a, p->p);
}
void list_print(struct node *n)
{
while ((n = n->n))
printf("%d ", n->i);
}
/* --- test case --- */
void fill_list_random(struct node *h)
{
int n = 20;
srand(time(NULL));
while (n--)
list_insert_after(h, list_new_node(rand() % 777));
}
void fill_list_array(struct node *h)
{
int i, arr[] = { 9, 11, 8, 3, 77, 8, 3, 42, 5, 34 };
for (i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i)
list_insert_after(h, list_new_node(arr[i]));
}
struct node *h;
int main()
{
h = list_new_head();
fill_list_random(h);
printf("Sorting: ");
list_print(h);
printf("\n\n");
list_qsort(h);
putchar('\n');
printf("Sorted: ");
list_print(h);
putchar('\n');
return 0;
}
/* --- step printing stuff --- */
/*
* keeps a list of nodes used as partitions, surrounds
* current partition with ':', old ones with '|'
*/
struct plist
{
struct node *p;
struct plist *n;
} *plist = NULL;
void plist_push(struct node *n)
{
struct plist *p = (struct plist *) malloc (sizeof (*p));
p->p = n;
p->n = plist;
plist = p;
}
int plist_isp(struct node *n)
{
struct plist *p;
for (p = plist; p; p = p->n)
if (p->p == n)
return 1;
return 0;
}
void list_qsort_print_step(struct node *p)
{
struct node *n = h;
while ((n = n->n))
if (n == p)
printf(" :%d:", n->i);
else if (plist_isp(n))
printf(" |%d|", n->i);
else
printf(" %d ", n->i);
plist_push(p);
putchar('\n');
}