Ｃ言語のリストのソートについて質問します。

質問

Ｃ言語のリストのソートについて質問します。
こんばんは、aida13です。以前の質問が自己解決しました。回答者のみなさん本当にすみませんでした。
今回はそのアルゴリズムで改善したい点がありましたので投稿させていただきました。以下のソートを実行するとソート自体はうまくいくのですが、見ての通りwhileやifなどを使って何度も実行しなおさないと完全にソートできません（「5 4 3 2 1」→「4 3 2 1 5」（一回ソート））。これを一回でソートできるようにしたいのです。また、降順も同様にそのままsecondとheadを入れ替えたのですが…今度は何度やっても「1 2 3 4 5」→「2 1 3 4 5」（一回ソート）からそれ以上動きません。アドバイスをお願いします。また、出来る限りこの形を保てる形でお願いします。

以下自作ソート
#include < stdio.h >
#include < stdlib.h >

struct ans
{
int data;
struct ans *next;
};

struct ans *sort_up(struct ans *head)
{
int temp;
struct ans *second_head;
second_head = (struct ans *)malloc(sizeof(struct ans));
second_head = head->next;

if( head->next == NULL )
{
return head;
}
else
{
if( head->data > second_head->data )
{
temp = head->data;
head->data = second_head->data;
second_head->data = temp;

sort_up(head->next);
}
else
{
sort_up(head->next);
}
return head;
}
}

struct ans *add_list(int x, struct ans *head)
{
struct ans *new_head;
new_head = (struct ans *)malloc(sizeof(struct ans));

new_head->data = x;
new_head->next = head;

return new_head;
}

void show_list(struct ans *head)
{
if( head == NULL )
{
printf("\n\n");
}
else
{
printf("%d ",head->data);
show_list(head->next);
}
}

void main()
{
struct ans *head;
head = NULL;

head = add_list(1,head);
head = add_list(2,head);
head = add_list(3,head);
head = add_list(4,head);
head = add_list(5,head);

do
{
printf("input:");
scanf("%d",&a);
if(a==0)
{
head = sort_up(head);
show_list(head);
}
}
while(a==0);
}

回答No.7

正親町（@Ohgimachi） · ベストアンサー

まずリストの操作では中のデータを操作してはいけません。この場合は単純ですが実際には構造が不明な場合が多いのです。ポインタを繋ぎかえるのが基本的です。

バブルソートは極めて簡単で単純に隣同士を入れ替えるだけです。

struct ans root;
struct ans *back,*temp,*last;

root.next=head;
last=NULL;

とすると内側のループは以下のように記述できます。(携帯からなのでコンパイルしていません)

for(back=&root;(head=(temp=head->next))!=last;back=temp)
　if(head->data<temp->data){
　　temp->next=head->next;
　　back->next=head;
　　head->next=temp;
　}

これを交換する最後のデータがリスト先頭に達するまで繰り返すだけです。
for(last=NULL;(head=root.next)!=last;last=temp)
・・・
return root.next;

バブルソートはデータが多いと直ぐ破綻しますが、とりあえず動くようにしてみてください。
動いたらバブルソートの改良、双方向リンク・リストに書き換えみる事です。

バブルソートは昇順に並べる場合には、交換が発生したときに最小値がどうか調べて、最小値を先頭に移動する事で実行時間の短縮ができます。また一度も交換が発生しなければ打ち切ります。

データが数万個以上でも実用的なソートもありますが、それはリンクの操作をマスターしてからですね。

お礼

ありがとうございます。やはり双方向リストを使わなければ無理なようですね。勉強して再チャレンジしてみたいと思います。

回答No.9

正親町（@Ohgimachi）

#7です。ミスがありました。
for(back=&root;(head=(temp=head->next))!=last;back=temp)
はfor(back=&root;(head=(temp=head)->next)!=last;back=temp)
です。(-o-;)

回答No.8

asuncion

＞挿入そのものは 2/n でも、

これを「２ぶんのエヌ」と読ませるのは至難の業です。
どう見ても「エヌぶんの２」としか読めません。

回答No.6

麻野 なぎ（@AsanoNagi）

済みません、訂正です。

挿入そのものは 2/n でも、それを n個分繰り返すから、全体のオーダーとしては n^2 ですね。
最近ぼけてます。

回答No.5

麻野 なぎ（@AsanoNagi）

挿入時にソートなら、挿入の前後でソートができているというのが仮定できるはずなので（少なくとも、挿入した後はソート済み……だから、ひとつ以上挿入したらその時点ではソート完了）処理オーダーはリストでも n / 2 の気がする。

先頭から確認して、大きい／小さい要素に突き当たったらそこに挿入……でいいのかな？

回答No.4

asuncion

＞「データを挿入するときにソート」したら n個のデータに対して n^2 時間かかるけど,
＞「データの挿入だけしておいてあとでソート」したら n log n 時間ですむから速いよね＞#1.

まあ、５件くらいのデータだからいいじゃないですか。

回答No.3

Tacosan

「データを挿入するときにソート」したら n個のデータに対して n^2 時間かかるけど, 「データの挿入だけしておいてあとでソート」したら n log n 時間ですむから速いよね＞#1.

さておき, このプログラムじゃダメダメですよ. sort_up でやってることって, しょせん「バブルソートの 1パス分」だけだもの. 手を動かして紙の上で実際にやってみましたか? あと, sort_up の
second_head = (struct ans *)malloc(sizeof(struct ans));
って何の意味があるの? その直後で second_head に代入してるから, これは結局システムを圧迫するためだけだよね?

ソートアルゴリズムなんかいっくらでもあるから, そのうち「リストに適切」なものをちゃんと調べて実装すればいいんだけどなぁ.

回答No.2

asuncion

＞両端にＮＵＬＬを置いてしまったらsort_up関数内の
＞　　　if( head->next == NULL )に引っかかってしまいそうな気もする

何をおっしゃっているのか、さっぱりわかりません。
双方向リストといってもいろんな考え方がありますが、
よくありそうなのは下記のとおりです。どこにも矛盾はないはずです。

先頭データ（仮に左端とします）のnextポインタ：左から２番目のデータを指す
先頭データのprevポインタ：NULL（先頭の左側にはデータがない）

最後尾（右端）データのnextポインタ：NULL（最後尾の右側にはデータがない）
最後尾データのprevポインタ：右から２番目のデータを指す

回答No.1

asuncion

そもそも、リスト構造は、構築した「後で」ソートするには
あまり向いていないデータ構造です。

データをリストに「挿入する」ときにソートするようにすれば、
すべてのデータを挿入した時点でソート済みのリストができあがっています。

逆順のソートがしたければ、双方向リストを作ればよいでしょう。

お礼

なるほど！確かに前のdataも見れるならうまくいきそうです。その場合前を見る(struct ans *prev)とするなら、(struct ans *next)をsort_up関数内で使った式でそのまま流用しても大丈夫でしょうか？

補足

考え方はわかりましたが、自分は双方向リストを使ったことがないので何とも…。両端にＮＵＬＬを置いてしまったらsort_up関数内の　　　　　　if( head->next == NULL )に引っかかってしまいそうな気もするんですが…