双方向循環リストにおける選択ソート

Question

前提・実現したいこと

双方向循環リストでの選択ソートを削除と挿入をもって実装したい。

発生している問題・エラーメッセージ

交換にあたるコードがわからない。
また、書いてみたが無限ループや完璧でないソートになった。

該当のソースコード

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

typedef struct node{
        struct node *prev;
        struct node *next;
        int value;
}NODE;

#define DUMMY -1
#define MAX 99
#define NUM 10

NODE* make_list(int num);
NODE* make_cell(int val);
void insert_cell_to_list(NODE *x, NODE *p);
NODE* delete_cell_from_list(NODE *x);
void print_list(NODE *link_list_head);
void free_list(NODE *link_list_head);
void selection_sort_cell(NODE *link_list_head);

int main(void){
        NODE *list_head;

        srand((unsigned int)time(NULL));

        list_head=make_list(NUM);
        printf("ランダムで作成したリストを表示\n");
        print_list(list_head);
        selection_sort_cell(list_head);
        printf("選択ソート後\n");
        print_list(list_head);
        printf("\n");

        free_list(list_head);

        return 0;
}

NODE* make_list(int num){
        NODE *list, *cel, *list_head;
        int i;

        list=make_cell(DUMMY);
        list->next=list;
        list->prev=list;
        list_head=list;

        for(i=0; i<num; i++){
                cel=make_cell(rand()%MAX);
                list=list->next;
                insert_cell_to_list(cel, list);
        }
        return (list_head);
}

NODE* make_cell(int val){
        NODE *p;

        p=(NODE*)malloc(sizeof(NODE));
        if (p == NULL) {
                fprintf(stderr, "Memory allocation error!\n");
                exit(-1);
        }
        p->value =val;
        p->next =NULL;
        p->prev =NULL;
        return(p);
}

void insert_cell_to_list(NODE *x, NODE *p){

  x->prev = p;
  x->next = p->next;
  p->next->prev = x;
  p->next = x;
}

NODE* delete_cell_from_list(NODE *x){

  x->prev->next = x->next;
  x->next->prev = x->prev;
  return (x);
}

void print_list(NODE *link_list_head){
        NODE *p;

        for (p = link_list_head->next; p != link_list_head; p = p->next) {
          printf("%d\n", p->value);
        }
}

void free_list(NODE *link_list_head){
        NODE *p, *q;

        p=link_list_head;
        p->prev->next = NULL;
        while (p!=NULL){
                q=p->next;
                free(p);
                p=q;
        }
}

void selection_sort_cell(NODE *link_list_head){
        NODE *p, *q, *low, *tmp;

        for (p = link_list_head->next; p != link_list_head->prev; p = p->next) {
          low = p;
          for (q = p->next; q != link_list_head; q = q->next) {
            if (low->value > q->value) {
              low = q;
            }
          }
          /* ここからソート(未完成) */
          tmp = delete_cell_from_list(low);
          insert_cell_to_list(tmp, p);
          tmp = delete_cell_from_list(p);
          insert_cell_to_list(tmp, low->prev);
          p = p->next;
        }
}

試したこと

ソート部分を自分が考えたように書いたが、うまくいかなかった。

Answer 1

もっと簡単になるかもしれませんが、とりあえずこれで OK なはず。

void selection_sort_cell(NODE *link_list_head){
        NODE *p, *q, *low, *tmp;

-        for (p = link_list_head->next; p != link_list_head->prev; p = p->next) {
+        for (p = link_list_head->next; p != link_list_head->prev; ) {
          low = p;
=====
          /* ここからソート(未完成) */
-          tmp = delete_cell_from_list(low);
-          insert_cell_to_list(tmp, p);
-          tmp = delete_cell_from_list(p);
-          insert_cell_to_list(tmp, low->prev);
-          p = p->next;
+			if (p == low)
+				p = p->next;
+			else {
+				NODE *prev = low->prev;
+				tmp = delete_cell_from_list(low);
+				insert_cell_to_list(tmp, p);
+				tmp = delete_cell_from_list(p);
+				if (p == prev)
+					insert_cell_to_list(tmp, low);
+				else
+					insert_cell_to_list(tmp, prev);
+				p = low->next;
+			}
        }
}

追記
for文はそのままで、「ここからソート(未完成)」の部分だけの変更でできます。

           /* ここからソート(未完成) */
-          tmp = delete_cell_from_list(low);
-          insert_cell_to_list(tmp, p);
-          tmp = delete_cell_from_list(p);
-          insert_cell_to_list(tmp, low->prev);
-          p = p->next;
+			if (p != low) {
+				NODE *prev = low->prev;
+				tmp = delete_cell_from_list(low);
+				insert_cell_to_list(tmp, p);
+				tmp = delete_cell_from_list(p);
+				if (p == prev)
+					insert_cell_to_list(tmp, low);
+				else
+					insert_cell_to_list(tmp, prev);
+				p = low;
+			}

追記2
もう少し簡単になりました。

          /* ここからソート(未完成) */
	        if (p != low) {
                tmp = low->prev;
                if (tmp == p) tmp = low;
                delete_cell_from_list(low);
                insert_cell_to_list(low, p);
                delete_cell_from_list(p);
                insert_cell_to_list(p, tmp);
                p = low;
            }

追記4
さらに簡単にできます。
if (p != low) { と} は無くても大丈夫です。

Comments

[submaru]

追記の方のコードを参考にさせてもらい変更したところ、正常に動くようになりました！わざわざ書いてくださってありがとうございました！

Answer 2

...a←→b←→c...A←→B←→C...とリストがあった時
bとBを交換する場合
(真面目にやる場合)

• bのprev/nextとBのprev/next をそれぞれ交換し
• a.nextとc.prevをBにして
• A.nextとC.prevをbにする。

(不真面目にやる場合)
b.valueとB.valueを交換する。

Comments

[submaru]

質問文の通り削除（取り出し）と挿入で行いたいのですが、その場合はどのようにするかはわかりますか？