クイックソート双方向リスト

Question

双方向リストのクイックソートにて
並び替えが以下のように上手くいかないです。

0 1 2 3 3 5 5 6 6 6 6 7 7 7 8 7 7 8 9 10 9

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

struct node {
    int data;
    struct node *prev;
    struct node *next;
};


void print_list(struct node *start);
void sort_list(struct node **arg_s, struct node **arg_e);
void swap(struct node **left, struct node **right);
void trade(struct node **l, struct node **r,struct node **s , struct node **e);

#define MAX 1000

int main(void) {
    struct node *start, *end, *new,*temp;
    int i;

    start = end = NULL;
    for (i = 0; i < MAX * 5; i++) {
        new = malloc(sizeof(struct node));
        if (new == NULL) {
            fprintf(stderr, "メモリ割り当て失敗\n");
            // ここで適切なクリーンアップを行う
            exit(EXIT_FAILURE);
        }
        new->data = rand() % MAX;
        new->prev = new->next = NULL;

        if (start == NULL) {
            start = end = new;
        } else {
            end->next = new;
            new->prev = end;
            end = end->next;
        }
    }

	
	printf("ソート前:\n");
	print_list(start);
	
	sort_list(&start, &end);

	printf("ソート後:\n");
	print_list(start);
    
    // メモリの解放処理
    while (start != NULL) {
        temp = start;
        start = start->next;
        free(temp);
    }

	return 0;
}

void print_list(struct node *start)
{
	struct node *p;
	
	p=start;
	while(p!=NULL)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}

void sort_list(struct node **arg_s,struct node **arg_e)
{
	struct node *start,*end,*left,*right,*s1,*s2,*e1,*e2;
	int pivot;
	
//引数を普通のポインタ型に変える
	start = *arg_s;
	end =*arg_e;

	left =start;
	right =end;
	
	//基準値を決定する。
	pivot=left->data;

	while(left!=right&&left->prev!=right)
	{
		//pivot以上が出るまで繰り返す。
		while(left->data < pivot)
		{
			left=left->next;
		}

　　　//pivot未満が出るまで繰り返す。
		while(right->data >pivot)
		{
			right=right->prev;
		}
		
		if(left->prev!=right&&left!=right)
		{
			//leftとrightを交換する。
			trade(&left,&right,&start,&end);
			//nextを代入する。
			left=left->next;
			right=right->prev;
		}
	}

	s2=right->next;
	e1=right;
	
	s1=start;
	e1->next=NULL;
	e2=end;
	e2->next=NULL;

	
	if(s1!=e1)
	{
		sort_list(&s1,&e1);
	}
	if(s2!=e2)
	{
		sort_list(&s2,&e2);
	}
	
	//連結し直す。
	e1->next=s2;
	s2->prev=e1;
	
	//戻り値を設定する
	*arg_s=s1;
	*arg_e=e2;
}


//leftとrightを交換する関数。
void trade(struct node **l, struct node **r,struct node **s , struct node **e)
{
	struct node *start,*end,*left,*right;
	
	//引数を普通のポインタ型に変える
	start = *s;
	end =*e;
	left =*l;
	right =*r;
	
	if(left == start)
	{
		start = right;
	}
	else
	{
		left->prev->next = right;	
	}

	// 後側要素を参照していたprevが、前側の要素を参照するように変更
	if(right == end)
	{
		end = left;
	}
	else
	{
		right->next->prev = left;
	}

	// start/endに関係ない部分を交換する
	left->next->prev = right;
	swap(&left->next, &right->next);
	right->prev->next = left;
	swap(&left->prev, &right->prev);
	swap(&left, &right);
	
	*l=left;
	*r=right;
	*s=start;
	*e=end;
}
		
// 構造体のポインタ同士を交換する関数
void swap(struct node **left, struct node **right)
{
	struct node *tmp;
	
	tmp = *left;
	*left = *right;
	*right = tmp;
}

Comments

[y_waiwai]

このままではコードが読みづらいので、質問を編集し、<code>ボタンを押し、出てくる’’’の枠の中にコードを貼り付けてください

[natsu158]

すみませんでした。

[kazuma-s]

回答するには、情報が不足しています。
struct node の定義がありません。
ex4.h の内容が分かりません。
main がありません。
データの入力がありません。

[Zuishin]

trade をやけにややこしくしていますが、ノードのつなぎ合わせをかえなくても data を取り換えるだけでよくないですか？

[natsu158]

data変えちゃダメだからです。

[Zuishin]

人に聞くのはいいんですか？

[natsu158]

ダメです。

Answer 1

質問のコードが消されてしまいましたが、trade関数がよくわからなかったのと、
リストのクイックソートに興味がわいたので、全部書き直してみました。

#include <stdio.h>   // printf
#include <stdlib.h>  // rand, srand
#include <time.h>    // time

#define MAX 1000
#define N   20 

struct node { int data; struct node *prev, *next; };

void print_list(struct node *p)
{
    for (; p; p = p->next) printf("%d ", p->data);
    putchar('\n');
}

void print_list_reverse(struct node *p)
{
	while (p->next) p = p->next;
	do printf("%d ", p->data); while (p = p->prev);
    putchar('\n');
}

struct node *insert(struct node *head, struct node *p)
{
	p->prev = NULL;
	p->next = head;
	if (head) head->prev = p;
	return p;
}

struct node *sort(struct node *head)
{
	if (!head->next) return head;

	int pivot = head->data;
	struct node *left = NULL, *right = NULL, *p, *next;

	for (p = head->next; p; p = next) {
		next = p->next;
		if (p->data < pivot)
			left = insert(left, p);   // pivot より小さいものは left へ
		else 
			right = insert(right, p);   // pivot 以上のものは right へ
	}
	if (left) left = sort(left);      // left があれば left をソート
	if (right) right = sort(right);   // right があれば right をソート

	head->next = right;               // pivot に right をつなぐ
	if (right) right->prev = head;    // pivot に right をつなぐ
	if (!left) return head;           // left が無ければ、pivot が先頭

	p = left;
	while (p->next) p = p->next;      // left の最後を探す
	p->next = head;                   // left に pivot をつなぐ
	head->prev = p;                   // left に pivot をつなぐ
	return left;                      // left が先頭
}

int main(void)
{
	srand((unsigned int)time(NULL));

	struct node *head = NULL, *tail = NULL;
	for (int i = 0; i < N; i++) {
		struct node *p = malloc(sizeof(struct node));
		p->data = rand() % MAX;
		p->prev = tail;
		p->next = NULL;
		if (tail) tail->next = p;
		else head = p;
		tail = p;
	}
	print_list(head);
	head = sort(head);
	printf("ソート後:\n"); print_list(head);
	printf("ソート後(逆順):\n"); print_list_reverse(head);
}

実行結果

614 876 377 404 59 252 277 661 563 169 49 746 384 449 624 344 826 491 173 981 
ソート後:
49 59 169 173 252 277 344 377 384 404 449 491 563 614 624 661 746 826 876 981 
ソート後(逆順):
981 876 826 746 661 624 614 563 491 449 404 384 377 344 277 252 173 169 59 49 

Comments

[natsu158]

わざわざありがとうございます。
参考にしてみます。