リスト構造を用いた挿入ソート

Question

不明点

c言語でリスト構造を用いた挿入ソートを作っています。
sort関数内に誤りがあり、segmentation faultを返してしまいます。
誤りを指摘していただければと思います。
よろしくお願い致します。

#include <stdio.h>
#include <stdlib.h>
  
typedef struct _cell {
	int element;
   	struct _cell *next;
}cell;
   
typedef struct _list{
	cell *head;
}list;
    
list* create() {
	list *L = (list *)malloc(sizeof(list));
	L->head = (cell *)malloc(sizeof(cell));
	L->head->next = NULL;
	L->head->element = -1;
	return L;
}
 
void addFirst(list *L, int element) {
	cell *add = (cell *)malloc(sizeof(cell));
	add->element = element;
	add->next = L->head->next;
	L->head->next = add;
}
    

    
void print(list *L) {
	cell *ptr = L->head->next;
	while(ptr != NULL) {
		printf("%d ", ptr->element);
        	ptr = ptr->next;
     	}
     	printf("\n");
}

void sort(list *L) {
	cell *ptr    = L->head->next->next;
	cell *prev = L->head->next;
	while(ptr != NULL){
		while(prev->element > ptr->element) {
			prev->next = prev;
			prev       = ptr;
         	}
			ptr  = ptr->next;
     	}
	printf("%d ", ptr->element);
}
    
int main() {
     	list *L = create();

     	addFirst(L, 5);
    	addFirst(L, 3);
     	addFirst(L, 5);
    	addFirst(L, 6);
     	print(L);
     	sort(L);
    
    	return 0;
}

Answer 1

Segmentation fault になる直接の原因はNULLアクセスだと思われます。
sort()の最後のprintf で ptr->element にアクセスしていますが ptr は while (ptr != NULL) を抜けた後なので NULL です。
このprintfの位置（タイミング）を見直せばそのエラーは解消できます。
しかしそもそもソート処理自体も正しく無さそうですよ。

Comments

[slushii]

もし良ければSORT処理の誤りも教えて頂けませんでしょうか？

[HiroshiWatanabe]

prev->next = prev; で prev の次が自分自身を指すようになってしまっていませんか？その後に prev = ptr; としているので次の while 時には prev->element > ptr->element は同じ物同士で比較しているので必ずfalseになりループ1回で抜けます。なのでそこで無限ループに陥るというトラブルには見舞われませんが、逆に言えばwhileループである意味も無いという理屈にならないでしょうか？これならwhileではなくifで良いという事になりますが恐らく繰り返したいのだろうと推察するとこの中で行うべき処理が足りないという想像に至ります。自分が想定しているアルゴリズム通りの処理になっているかを落ち着いて見直してみてください。

[slushii]

ひどいコードですみませんでした。ご丁寧にありがとうございました。

Answer 2

連結リストのソートは難しいと言うか結構やっかいですね。
私もかなり探したのですが、配列を対象にしたソートのサンプルプログラムでしたらいくらでも見つかりますが、連結リストのサンプルプログラムはあまりありませんでした。

ソートの方法は配列の場合と同じようにいろいろありますが、（配列の場合と同じやり方の）挿入ソートで単方向リストをソートしようとすると結構大変です。

発想を変えて（と言うと大げさですが）新たにリストを作っていくのが実装としては楽ではないかと思います。幸いに連結リストはリンクの付け替え（張り替え）は自由に（しかも低コストで）できますので、元のリストからノードを切り離し新規リストに昇順（或いは降順）を保つように追加していればいいです。

別の方法として、元のリストから最大の（或いは最小の）ノードを選んで、新規リストの先頭に追加していくというやり方もあります。こっちの方がちょっと速いみたいです。

なお、連結リストのソートはマージソートが比較的速いようです。