クイックソート リスト構造体

Question

リスト構造体に入力された情報を昇順、降順に並べ替えたいです。

リスト構造体をクイックソートをつかって昇順、降順に並び替えたいです。
クイックソートを使うには基準値を決める必要があると、学んだのですが、リストの数が変化する中で、どう基準値を決め、並び替える方法を知りたいです。
そもそもリスト構造体をクイックソートで並び替えれるのでしょうか？

以下並び替えたいリスト構造体のコードです。

該当のソースコード

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define NO_PROBLEM 0
#define ERROR 1

typedef struct student
{
int id;
char name[10 + 1];
struct student *next;
} PERSON_t;

static PERSON_t *head = NULL;
static PERSON_t *tail = NULL;
int add_person(int id);
int sort_person(void);
void get_string(char *str, unsigned int num);
int get_person_id(PERSON_t *p);
int get_person_name(PERSON_t *p);

int main(void)
{
	int number = 0;
	int id = 0;
	int ret;
	int end_flag = 0;
	while(end_flag == 0)
	{
		printf("1追加入力\n2ソート\n0.終了\n ");
		scanf("%d",&number);
		fflush(stdin);
		switch(number){
			case 1:
				id++;
				ret = add_person(id);
				if(ret == NO_PROBLEM){
					puts("追加完了");
				}
				break;
			case 2:
				ret = sort_person();
				if(ret == NO_PROBLEM){
					puts("並べ替え完了");
				}
			break;
				default:
			break;
		}
	}
	return 0;
}

int sort_person(void){
	return 0;
}

int add_person( int id)
{
	PERSON_t *data;
	int ret = NO_PROBLEM;
	data = (PERSON_t *)malloc(sizeof(PERSON_t));
	data->id = id;
	printf("ID→");
	printf("%d\n",data->id);
	get_person_name(data);
	if (head == NULL)
	{
		head = data;
		tail = data;
	}
	else
	{
		tail->next = data;
		tail = data;
	}
	tail ->next = NULL;
	return ret;
}

void get_string(char *str, unsigned int num)
{
	int i = 0;
	int c = 0;
	memset(str, 0, num );
	while (strlen(str) < num - 1 )
	 {
		c = getchar();
		if (c != '\n') {
			str[i] = c;
			i++;
		} else {
			break;
		}
	}
}

int get_person_name(PERSON_t *p){
	int ret = NO_PROBLEM;
	printf("名前→");
	get_string( p->name, sizeof p->name );
	return ret;
}

補足情報（FW/ツールのバージョンなど）

windows10 Cpad

Comments

[1T2R3M4]

https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q13243196503

以下ご対応ください。
https://teratail.com/help#posted-otherservice

[cat_is_freedom]

認識しておりませんでした。
対応いたします。

Answer 1

リストのクイックソートやってみました。

#include <stdio.h>   // printf, scanf, putchar, puts
#include <string.h>  // strcmp
#include <stdlib.h>  // malloc

#define NO_PROBLEM 0

typedef struct student {
	int id;
	char name[10 + 1];
	struct student *next;
} PERSON_t;

static PERSON_t *head = NULL;
static PERSON_t *tail = NULL;

int add_person(int id);
int sort_person(void);
PERSON_t * quick_sort(PERSON_t *a);
void print_person(PERSON_t *p);

int main(void)
{
    int number = 0;
    int id = 0;
    while (1) {
        printf("1.追加入力  2.ソート  3.表示  0.終了: ");
        scanf("%d", &number);
        switch (number) {
		case 0:
			return 0;
		case 1:
			if (add_person(++id) == NO_PROBLEM) puts("追加完了");
			break;
		case 2:
			if (sort_person() == NO_PROBLEM) puts("並べ替え完了");
            break;
		case 3:
			print_person(head);
        }
    }
}

#define add(q) (p = a, a = a->next, p->next = q, q = p)

PERSON_t * quick_sort(PERSON_t *a)
{
	if (a == NULL || a->next == NULL) return a;
	PERSON_t *pivot = a, *less = NULL, *greater = NULL, *p;
	a = a->next;
	pivot->next = NULL;
	while (a) {
		int diff = strcmp(a->name, pivot->name);
		if (diff < 0) add(less);
		else if (diff > 0) add(greater);
		else add(pivot);
	}
	less = quick_sort(less);
	greater = quick_sort(greater);
	if (less == NULL) a = pivot;
	else {
		for (a = p = less; p->next; p = p->next) ;
		p->next = pivot;
	}
	for (p = pivot; p->next; p = p->next) ;
	p->next = greater;
	return a;
}
	
int sort_person(void)
{
	head = quick_sort(head);
    return NO_PROBLEM;
}

int add_person(int id)
{
    PERSON_t *data;
    data = (PERSON_t *)malloc(sizeof(PERSON_t));
    data->id = id;
    printf("ID->%d\n", data->id);
	scanf("%10s", data->name);
	data->next = NULL;
	tail = head ? tail->next = data : (head = data);
    return NO_PROBLEM;
}

void print_person(PERSON_t *p)
{
	for (; p; p = p->next) printf(" %s", p->name);
	putchar('\n');
}

実行例

1.追加入力  2.ソート  3.表示  0.終了: 1
ID->1
ccc
追加完了
1.追加入力  2.ソート  3.表示  0.終了: 3
 ccc
1.追加入力  2.ソート  3.表示  0.終了: 1 aaa
ID->2
追加完了
1.追加入力  2.ソート  3.表示  0.終了: 3
 ccc aaa
1.追加入力  2.ソート  3.表示  0.終了: 1 ddd
ID->3
追加完了
1.追加入力  2.ソート  3.表示  0.終了: 1 bbb
ID->4
追加完了
1.追加入力  2.ソート  3.表示  0.終了: 3
 ccc aaa ddd bbb
1.追加入力  2.ソート  3.表示  0.終了: 2
並べ替え完了
1.追加入力  2.ソート  3.表示  0.終了: 3
 aaa bbb ccc ddd
1.追加入力  2.ソート  3.表示  0.終了: 0

バグがあるかもしれません。どうでしょうか？

追記
コードの説明です。
変数名{変数の値}。値がポインタの時は * で -> の先のオブジェクトを指す。
->{構造体の値} は一つ前の * で指されるオブジェクト。

head{}->{1,"ccc",}->{2,"aaa",}->{3,"ddd",}->{4,"bbb",NULL}
というリストができたとする。

quick_sort に入ると、
a{}->{1,"ccc",}->{2,"aaa",}->{3,"ddd",}->{4,"bbb",NULL}

pivot = a, a = a->next, pivot->next = NULL; を実行すると、
pivot{}->{1,"ccc",NULL}
a{}->{2,"aaa",}->{3,"ddd",}->{4,"bbb",NULL}

a のリストの先頭から順番に取り外し、
pivot の "ccc" より小さい name のものを less リストに追加し、
pivot の "ccc" より大きい name のものを greater リストに追加する
ということを繰り返す。

int diff = strcmp(a->name, pivot->name); を実行すると、
"aaa" < "ccc" だから diff は負の値で、a の先頭を less に追加する。
add(less) は、 p = a, a = a->next, p->next = less, less = p なので、
p{}->{2,"aaa",NULL}　　(less は NULL だったので)
a{}->{3,"ddd",}->{4,"bbb",NULL}
less{}->{2,"aaa",NULL}

int diff = strcmp(a->name, pivot->name); を実行すると、
"ddd" > "ccc" だから diff は正の値で、a の先頭を greater に追加する。
add(greater) は、 p = a, a = a->next, p->next = greater, greater = p なので、
p{}->{3,"ddd",NULL}　　(greater は NULL だったので)
a{}->{4,"bbb",NULL}
greater{*}->{3,"ddd",NULL}

int diff = strcmp(a->name, pivot->name); を実行すると、
"bbb" < "ccc" だから diff は負の値で、a の先頭を less に追加する。
add(less) は、 p = a, a = a->next, p->next = less, less = p なので、
p{}->{4,"bbb",}->{2,"aaa",NULL}　　(less の先頭に追加)
a{NULL}
less{}->{4,"bbb",}->{2,"aaa",NULL}

a が NULL なので、while (a) のループを終了

less = quick_sort(less) で less をソート
less{}->{2,"aaa",}->{4,"bbb",NULL}

greater = quick_sort(greater) で greater をソート
greater{*}->{3,"ddd",NULL}

less が NULL なら、a は pivot + greater となるが、
less が NULL でないので、a = less とし、
less と pivot と greater を結合して a を作る。
for (p = less; p->next; p = p->next) ; で、
p が less の最後の要素を指すようにする。
p->next = pivot で less の最後に pivot を連結する。
for (p = pivot; p->next; p = p->next) ; で、
p が pivot の最後の要素を指すようにする。
p->next = greater で pivot の最後に greater を連結する。

return a; でソートと連結が完了したリストを返す。

Comments

[cat_is_freedom]

解答ありがとうございます！
触ってみたところきちんと動きました。
しかし、初心者の私には、コードが省略？して書かれているところが多くあり、理解しきれないところがありました…
あとは、リストがないときに何か表示させる必要があるのかな、と思いました。
参考にさせていただきます。

[actorbug]

Prolog の差分リストを応用すれば、最後にリストをたどらなくてよくなりますね。

#define add(q) (*q = a, q = &a->next, a = a->next)

PERSON_t* quick_sort(PERSON_t* a, PERSON_t* last)
{
if (a == NULL) return last;
PERSON_t *pivot = a, *less, *greater;
PERSON_t **pivot_last = &a->next, **less_last = &less, **greater_last = &greater;
a = a->next;
while (a) {
int diff = strcmp(a->name, pivot->name);
if (diff < 0) add(less_last);
else if (diff > 0) add(greater_last);
else add(pivot_last);
}
*less_last = *greater_last = NULL;
*pivot_last = quick_sort(greater, last);
return quick_sort(less, pivot);
}

int sort_person(void)
{
head = quick_sort(head, NULL);
return NO_PROBLEM;
}

[cat_is_freedom]

解答ありがとうございます！
ポインタのポインタが出てきて頭が整理する必要があり、自分の力のなさを感じます。。。
とても見やすいコードなので、参考にさせてください。

[cat_is_freedom]

また質問になるのですが、
tail = head ? tail->next = data : (head = data);
を違う形に書き直すとどうなりますでしょうか？
調べたところ、「真の時は前式を、偽の時は後式を代入」
と書いてありましたが、if文で書き直せるのでしょうか？

[kazuma-s]

if (head != NULL)
. tail = tail->next = data;
else
. tail = head = data;
質問の次のコードと同じです。
if (head == NULL) {
. head = data;
. tail = data;
} else {
. tail->next = data;
. tail = data;
}

[cat_is_freedom]

もし可能でしたら、コードに解説など入れていただけないでしょうか？
プログラムはきちんと動くのですが、なかなか理解しきれません。。。
お時間がありましたら、よろしくお願いいたします。

[cat_is_freedom]

丁寧に解説までしてくださりありがとうございました。

Answer 2

そもそもリスト構造体をクイックソートで並び替えれるのでしょうか？

やれなくはないがリストにクイックソートは向いてない。

クイックソートは集合の要素を飛び飛び(ランダム)にアクセスします。
リストは次の要素/前の要素を順にアクセスできますが、
n番目の要素はアタマから次の要素をn回辿らにゃなりませんから。

リストを対象とした速いソートというと...マージソートあたりですかね。