連結リストのソート

C入門、プログラミング入門として、連結リストの次に基本的なソートをやってみようと少し格闘してみた。単純なint配列とかじゃテキストのままなので、どうせだったら連結リストを並べ変えてみようと思ったのが間違いだった。

まず、いちばん簡単なのは隣り合うノードを入れ替えるswap関数を作ることかと思った。ある世代以降のCでは構造体同士の代入ができるらしいので、もしかしてポインタ入れ替えよりも、ごそっとデータを入れ替えるのが正解なのかと一瞬思ったけど、さすがにそれじゃリストの意味がない。

ともあれ、swap関数さえあれば、後はリストを順にたぐりつつ入れ替えればバブルソートはすぐできるはず。でも、考えてみると、2個のノードを入れ替えるといってもそれらが隣接するノードとの配線もあるので、どうも単純じゃない。しかも、先頭はlist->headと特殊なポインタで参照されていたり、最後はNULLで終わっていたり、そもそもノード数が1個、2個といことだってあるので、その場合分けも必要そう、とか考えると思ったより面倒そう。

それで、もうswapとか汎用関数を作るより、いきなりsort関数を作った方が楽だろと思って、やってみようとしたけど、どうもややこしくて途中で挫折した。

void SortList(List *list) {
  Node *top, *tail, *l, *r;

  // if it's null or just a node. 

  if ((list->head == NULL) ||
      (list->head->next == NULL)) {
    return;
  }

  // compare and swap the first two anyways. 

  if (list->head->data.size > list->head->next->data.size) {
    top = list->head; // to 0
    tail = list->head->next->next;
    list->head = list->head->next;
    list->head->next = top;
    list->head->next->next = tail;
  }

  // if that's all there is. 

  if (tail == NULL) {
    return;
  }

  // continue sorting... 

  top = list->head->next;
  l = top->next;
  r = l->next;
  tail = r->next;

  while (tail != NULL ) {
    if (l->data.size > r->data.size) {
    }
    top = l; l = r; tail = r; tail = r->next;  // slide them all
  }
}

ほんとはpthreadってやつを試してみるために、マージソートをやってみようと思っていたのに、バブルソートすら難しい。ソート結果を入れるリストを別に用意して、挿入ソートなら比較的簡単にできそうな気がするんだけど、うーむ。