双方向リストのインサートソート

タイトル通りなんですけどだいぶ苦労しました...
以下コードです

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX 30
typedef struct link_tag{
  struct link_tag *next;
  struct link_tag *prev;
  int id;
}linked_list;
void delete_element(linked_list*,int);
void insert_sort(linked_list*);
void insert_list(linked_list*,linked_list*);
void sub_sort(linked_list*,linked_list*);
void regist_element(linked_list*,linked_list*);
linked_list* head_point(linked_list*);
linked_list* create_element(int);
int main()
{
  int i;
  linked_list *head,*p;
  head = create_element(rand()%MAX);
  p = head;
  srand((unsigned)time(NULL));
  for(i=0;i<MAX;i++){
    regist_element(head,create_element(rand()%MAX));
  }
  while(head->next){
    printf("%d ",head->id);
    head = head->next;
  }
  printf("\n");
  printf("sorted : \n");
  insert_sort(p);
  while(p->prev)
    p = p->prev;
  while(p){
    printf("%d ",p->id);
    p = p->next;
  }
  printf("\n");
  return 0;
}

linked_list* create_element(int id)
{
  linked_list* new;
  if(!(new = (linked_list*)malloc(sizeof(linked_list)))){
    fprintf(stderr,"failed secure memory\n");
    exit(1);
  }
  new->next = NULL;
  new->prev = NULL;
  new->id = id;
  return new;
}
void regist_element(linked_list* former,linked_list* latter)
{
  if(former->next)
    regist_element(former->next,latter);
  else
    {
    former->next = latter;
    latter->prev = former;
    }
}

void insert_sort(linked_list* p)
{
  linked_list* head = p,*n,*sent;
  p = head->next;
  sent = head;
  head->next = NULL;
  while(p){
    n = p->next;
    sub_sort(head,p);
    while(head->next)
      head = head -> next;
    p = n;
  }
}

void sub_sort(linked_list *p,linked_list *el)
{
  while(p){
    if(p->id > el->id){
      if(p->prev)
        p = p->prev;
      else{
        p->prev =el;
        el->prev = NULL;
        el->next = p;
        return;
      }
    }
    else
      break;
  }
    insert_list(p,el);
}

linked_list* head_point(linked_list* p)
{
  if(!p){
    fprintf(stderr,"error null pointer \n");
    exit(1);
  }
  while(p->prev != NULL)
    p = p->prev;
  return p;
}

void insert_list(linked_list* p,linked_list* t)
{
  if(p->next){
    t->next = p->next;
    p->next->prev = t;
  }else
    t->next = NULL;
  p->next = t;
  t->prev = p;
}

実行結果

23 2 17 24 10 5 25 0 8 20 25 23 5 13 17 7 8 12 19 2 14 19 1 20 28 14 21 10 6 16
sorted :
0 1 2 2 5 5 6 7 8 8 10 10 12 12 13 14 14 16 17 17 19 19 20 20 21 23 23 24 25 25 28

いろいろな関数がずら～～っと並んでいますが双方向リストの特徴がよくでているのはこの部分

void insert_sort(linked_list* p)
{
  linked_list* head = p,*n,*sent;
  p = head->next;
  sent = head;
  head->next = NULL;
  while(p){
    n = p->next;
    sub_sort(head,p);
    while(head->next)
      head = head -> next;
    p = n;
  }
}

～～

void insert_list(linked_list* p,linked_list* t)
{
  if(p->next){
    t->next = p->next;
    p->next->prev = t;
  }else
    t->next = NULL;
  p->next = t;
  t->prev = p;
}

C言語標準搭載の配列とは違い、双方向リストでの要素の挿入はアドレスの付け替えになります。insert_list関数ではpが指す構造体のちょうど後ろに要素を挿入する関数になっています。後ろに挿入する関数があるなら前に挿入する関数もあればいいな、って今気づきました。気づかなかったので前に挿入しないといけない場合はインサートソート関数内部で場合分けしてあります...
さらに、インサートソート関数は子関数としてsub_sortをつけてサブルーチン化を計っていたんですが、これがなかなかに曲者でした。インサートソートはソート済配列に挿入するアルゴリズムなので、はじめにhead->next=NULL;として、まず整列済のリストとして壁を作ってあります。このソートされたエリアとそうでないエリアを行き来するのがポイントなんですが、何度やっても無限ループ。sub_sort関数を呼び出した後と前ではp->nextが指すものが全く違っていることに気づくのにかなりの時間がかかりました。その結果、nという一時ポインタに次に挿入する要素を記憶しておくようにしました。
void delete_element(linked_list*,int)関数は作ろうと思ってたんですけどなんかもう体力がないっす...
大番長やろ