C言語でリストのソートについて質問します。以下のmain()文を用いた

質問

C言語でリストのソートについて質問します。以下のmain()文を用いた昇順、降順のソートを行いたいのですが、何度やってもうまくいくアルゴリズムが組めません。アドバイスお願いします。

void main()
{
struct *head;

head = NULL;

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

show_ans(head);

head = sort_up(head);

show_ans(head);

head = sort_down(head);

show_ans(head);
}

以下自作のソートです。穴だらけですが…

struct ans *sort_up(struct ans *head)
{
struct ans *info;
struct ans *move_info;
struct ans *keep;
struct ans *temp;

for(info = head; info->next!=NULL; info=info->next)
keep = info;
for(move_info = info->next; move_info!=NULL; move_info->next)
{
if(info > info->next)
{
temp = info->next;
info->next = info;
info = temp;
head = info;
}
}
return head;
}

回答No.1

kmee · ベストアンサー

まずは、新しいソートアルゴリズムを研究しているのでなければ、既存のアルゴリズムをよく理解することです。

また、
A→B→C→D
このような単方向リストでBとCを入れ替える場合

A->next=C
C->next=B
B->next=D
の3つの操作が必要です。

プログラムを見ると、 A->next=Cにあたるものがありません。
head=info; とありますが、headの初期値リストの先頭をあらわしているはずなので、かならずしも「直前」の要素ではないです。これを変えてしまったら、迷子になる要素が出てきます。

> keep = info;
> for(move_info = info->next; move_info!=NULL; move_info->next)

forループの最後がおかしいです。これでは「何もしない」と同じです。
また、move_infoが以降まったく使われていません。このループは特殊は場合を除いて無限ループになります。

また、keepも以降まったく使われていません。move_infoのループの後で、infoのループの元の位置に戻そうという考えなのでしょうが、順番が入れ替わっている可能性があり、「前回の続き」という使いかたには不向きです。

実際のところ、ランダムアクセスを使う配列のソートのアルゴリズムは、シーケンシャルアクセスが基本のリスト構造には不向きです。
マージソートを使ってみてください。配列で苦労したマージ操作が、リスト構造では簡単に書けます。

あとは、add_ansの実装方法も気になります。
malloc等で動的に確保しているのなら、対応するfreeを実行する関数も用意した方がいいです。
これくらいの長さですぐ終了するプログラムなら影響は無いでしょうが。

補足

回答ありがとうございます。手抜きになってしまっていてすみません。とりあえずすべてのソースを載せておきます。マージソートに関しては見様見真似でやってみましたが結果「１」しか帰ってきませんでした…

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

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

void main()
{
struct ans *head;

head = NULL;

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

show_ans(head);
head = merge_sort(head);
show_ans(head);
}

struct ans *add_ans(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_ans(struct ans *head)
{
if( head == NULL )
{
printf("\n\n");
}
else
{
printf("%d ",head->data);
show_ans(head->next);
}

struct ans *merge_ans(struct ans *head, struct ans *y)
{
struct ans z,*p;

p = &z;

while( head != NULL && y != NULL )
{
if( head->data <= y->data )
{
p->next = head;
p = head;
head = head->next;
}
else
{
p->next = y;
p = y;
y = y->next;
}
}

if( head == NULL )
{
p->next = y;
}
else
{
p->next = head;
}
return z.next;
}

struct ans *merge_sort(struct ans *head)
{
struct ans *a,*b,*y;

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

a = head;
b = head->next;

if( b != NULL )
{
b = b->next;
}

while( b != NULL )
{
a = a->next;
b = b->next;
if( b!= NULL )
{
b = b->next;
}
}

y = a->next = NULL;
a->next = NULL;

return merge_ans( merge_sort(head), merge_sort(y));
}

回答No.3

Tacosan

y = a->next = NULL;
ってどういうこと?

お礼

回答ありがとうございます。申し訳ないですが、自分で書いていて中身がこんがらがってしまい意味不明な内容になってしまいました。ですので、一旦自分で納得できるようなアルゴリズムを組んでから再度質問させていただきます。本当にすみませんでした。

回答No.2

asuncion

＞以下のmain()文を用いた

それは必須条件ですか？
main文ではなくてmain「関数」ですけどね。
それにしたところで、

＞struct *head;

こういう変数定義はできないですね。
どういうメンバー構成を持つ構造体へのポインタであるかが全くわかりません。

＞struct ans *sort_up(struct ans *head)

ans構造体のメンバー構成は？

補足

回答ありがとうございます。補足は2人目の回答者の方の方に載せさせていただきます。