構造体配列のクイックソート

質問

こんにちわ。

構造体配列のリストを　ポインタのつなぎ変えによるクイックソートで
以下のようなソートをしたいのですが、悩んでおります。

struct info {
int count;
struct info *prev;
struct info *next;
};

int main () {

struct info info[5];

/* 初期値設定 */
quick_sort(info, 0, 5);

return 0;
}

上記のようにして、クイックソートをしたいのですが、
よくあるクイックソートだと　例えば初期値を
＜配列のindex＞要素の値を

<0> <1> <2> <3> <4>
5 1 4 3 2

などと定義した場合　普通のクイックソートだと

<0> <1> <2> <3> <4>
1 2 3 4 5

というように並び変えられてしまい

＜配列のindex＞と　要素の値の組み合わせが変わってしまいますが、
この組み合わせを変えず、

struct info *if;

if = info;

for (i=0; i<MAX; i++){
printf("%d", if->count);
if = if->next;
}
printf("\n");

とすることで、indexとしては昇順になっていないが
*nextをたどっていくことでちゃんと目的の値の昇順になっている
というのを実現したいのですが、ポインタのつなぎ変えか何かが
間違っているようで　うまいことできていません。

どなたかご教授いただけますでしょうか。

申し訳ありませんが、よろしウお願いいたします。

回答No.7

rinkun

一般論です。平均オーダーはクイックソート、マージソートともO(n*log(n))で同等ですが、係数はクイックソートの方が小さく、一般に倍ほど速いといいます。ただ最悪時はクイックソートがO(n^2)と悪化するのに対してマージソートは最悪でもO(n*log(n))で安心できます。
またクイックソートは評価値が同じ項目の順序が安定しない性質があるので、複数の評価値で順にソートする場合には向きません。
こういった特徴もあり、Javaのライブラリなどでは、基本型はクイックソート、オブジェクト型はマージソートをベースとするアルゴリズムを使っています。リンクリストならマージソートの方がお勧めできるかと思います。

回答No.6

yaemon_2006

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

typedef struct list{
int no;
char name[8];
struct list *next;
} list;

void printlist(list *head)
{
while(head){
printf("(%d %s)", head->no, head->name);
head = head->next;
}
putchar('\n');
}

void printarray(const list *l, int n)
{
int i;

for(i = 0; i < n; ++ i) printf("(%d %s)", l[i].no, l[i].name);
putchar('\n');
}

list *q_Sort(list *head)
{
if(head && head->next){
list *l = NULL, *m, *r = NULL, *k, *p;

m = k = head;
head = head->next;
k->next = NULL; /* 念のため */
while(head){
p = head;
head = head->next;
if(p->no < k->no) p->next = l, l = p;
else if(p->no == k->no) p->next = m, m = p;
else p->next = r, r = p;
}
if(head = q_Sort(l)){
for(p = head; p->next; p = p->next) ;
p->next = m;
}
else head = m;
k->next = q_Sort(r);
}
return head;
}

int main(void)
{
list l[] = {{0, "a"}, {0, "b"}, {0, "c"}, {0, "d"}, {0, "e"},
{0, "f"}, {0, "g"}, {0, "h"}, {0, "i"}, {0, "j", NULL}};
list *head;
const int n = sizeof l / sizeof l[0];
int i;

srand((unsigned)time(NULL));
for(i = 0; i < n - 1; ++ i) l[i].no = rand() % 10, l[i].next = l + i + 1;
l[i].no = rand() % 10;
head = q_Sort(l);
printlist(head);
printarray(l, n);
return 0;
}

回答No.5

Tacosan

クイックソートは本質的にシーケンシャルアクセスしか使わないので, 双方向リストに適用することも (一応は) 可能ですよ＞#3.
ただ「同じ値もかなり含まれると思う」というのはちょっと不安. ピボットとして「先頭と中間と末尾の値の平均」を使ってるけど, 「ソートしようとしている部分」がすべて同じ値だった場合, 当然これらはすべて同じ値であり, したがってピボットの値も同じになります. ところが, そのような場合クイックソートの性能は最悪になる可能性があります.
「どんなデータが来てもそれなりに効率的に実行できる」という意味ではマージソートの方が安心できるかなぁ.

回答No.4

trapezium

> あ、また、どうしても　qsortなどの既存関数は使えず、全て自分で

qsort() は説明で出しただけで、実際は御自分の実装に置き換えることを想定しています。

> 中身全体を変えるのではなく、順番構成となるポインタ値だけを変更して

info[] の中身自体は操作していません。

for (i = 0; i < 5; i++)
printf("%d:%d ", i, info[i].count);

なので、もとの順が欲しければ info[] でアクセス、ソート済が欲しければ ap[] 経由、next,prev を使いたければ、ap[] 経由で設定してやれば、もう ap は free() してかまいません。割とよくやる手順だと思いますが。

回答No.3

tossy2011

双方向リストの場合配列の添え字でアクセスできないので
基本的にクイックソートはあんまり使わないと思います。
マージソートでは駄目なのでしょうか？

補足

ご回答　ありがとうございますm(_ _)m

実際には、かなり大量なデータをソートしなければならなくなるのですが、また、同じ値もかなり含まれると思うのですが、この場合、効率的には　クイックソートとマージソート　どちらのほうがよいのでしょうか？

もともとクイックソートを選んだのは　あまり知識がなかったためでもあり、効率的に変わらず、下記に示しましたことが実現できるのであればマージソートにしたいと思います。これからまた勉強しなければなりませんが(^^；

あの、ちなみに、この一番の問題となっております、構造体配列のindexと、
構造体内の変数の値の組み合わせは変えたくなく、構造体内のprev, next変数の値の変更によるポインタの繋ぎ変えだけで　ソートを実現したいのですが、
そのための注意事項や　実現の仕方について　少し具体的にアドバイスいただくことはできますでしょうか(>_<)

もしトンチンカンなことを言っていたらすみません；

回答No.2

trapezium

どうしてもポインタのリンクでやりたいのでしたら、無視してくれてかまいませんが、単に間接参照したのではダメなのですか？

こんな感じ。なんかあれば補足してください

typedef struct info {
int count;
struct info *prev;
struct info *next;
} * info_t;

int
icmp(void const *a, void const *b)
{
info_t const *a1 = a;
info_t const *b1 = b;
return (*a1)->count - (*b1)->count;
}

struct info info[] = {{5}, {1}, {4}, {3}, {2}};

int
main(int argc, char *argv[])
{
int i;
info_t ap[5];

for (i = 0; i < 5; i++)
ap[i] = info + i;
qsort(ap, 5, sizeof(ap[0]), icmp);

printf("info[]: ");
for (i = 0; i < 5; i++)
printf("%d:%d ", i, info[i].count);

printf("\n *ap[]: ");
for (i = 0; i < 5; i++)
printf("%d:%d ", i, ap[i]->count);
printf("\n");
return 0;
}

補足

さっそくの回答　ありがとうございますm(_ _)m
実は　都合上　どうしても　配列のindexと、中身の値の組み合わせは
変えたくないのです(>_<)

その場合は、ポインタの繋ぎ変えを行うしかないかと思ってまして。

例えば
array[0] = { (int count=)5, (*prev=)Aprev, (*next=)Anext }
array[5] = { (int count=)2, (*prev=)Bprev, (*next=)Bnext }

だとして、このふたつのリスト中での位置を逆転させたいとしたら
array[0] = { (int count=)5, (*prev=)Bprev, (*next=)Bnext }
array[5] = { (int count=)2, (*prev=)Aprev, (*next=)Anext }

というような感じにしたいのです(>_<)
つまり、普通に中身だけ交換していくクイックソートのアルゴリズムのやつを
中身全体を変えるのではなく、順番構成となるポインタ値だけを変更して
ソートを行いたく、つまり、ソート後に

for (i = 0; i < 5; i++)
printf("%d:%d ", i, ap[i]->count);

というような表示を行った場合は、依然　5 1 4 3 2 と表示され
ap = ap->next;

とした時に　目的の値の昇順に表示される　というようなものを
目指しているのですが、そのような場合　ポインタの繋ぎ変え方や
再帰呼び出しのところでの引数にとまどっております(>_<)

あ、また、どうしても　qsortなどの既存関数は使えず、全て自分で
書かなければならないのです(>_<)

なんだか注文が多くてすみません(>_<)

回答No.1

asuncion

＞ポインタのつなぎ変えによるクイックソート

っていうのが今ひとつうまくイメージできませんが、
何はともあれ、ソースコード全体を見せてください。
そうすれば、何かが見えてくるかもしれません。

お礼

あ、すみません、pだのheadだのは　さきほど奮闘中に　このようにポインタの繋ぎ変え？でソートを行う場合　headを用意していないと　先頭がどこか分からなくなる　というような記述をネットで目にしまして　試行錯誤中のため書いてしましましたが、

p = &head;
p->next_nb_info = left0;
p = left0;

は　無視していただいてかまいません；；

必要であれば、そのようにコメントしていただいてもかまいません；；

補足

こちらも　さっそくの回答　ありがとうございますm(_ _)m

#include <stdio.h>

#define MAX_IDX 6

struct nb_info {
int ec;
struct nb_info *prev_nb_info;
struct nb_info *next_nb_info;
};

int j = 0;

void quick_sort(struct nb_info *left_nb_info, struct nb_info *right_nb_info, int i_left, int i_right)
{
int left = i_left;
int right = i_right;
struct nb_info *left0;
struct nb_info *right0;
struct nb_info *nb_left, *nb_center, *nb_right;
struct nb_info head, *p;
int pivot;
int i;

left0 = left_nb_info;
right0 = right_nb_info;

p = &head;
p->next_nb_info = left0;
p = left0;

nb_left = left_nb_info;
nb_right = right_nb_info;
nb_center = nb_left;

for (i = 0; i < (right-left)/2; i++)
nb_center = nb_center->next_nb_info;

if (left >= right)
return;

pivot = (nb_left->ec + nb_center->ec + nb_right->ec)/3;

while (1) {
struct nb_info tmp;
struct nb_info *tmp_prev;
struct nb_info *tmp_next;

while (nb_left->ec < pivot) {
left++;
nb_left = nb_left->next_nb_info;
if (nb_left == NULL)
break;
}
while (nb_right->ec > pivot) {
right--;
nb_right = nb_right->prev_nb_info;
if (nb_right == NULL)
break;
}
if (left >= right)
break;

tmp = *nb_left;
*nb_left = *nb_right;
*nb_right = tmp;

tmp_prev = nb_left->prev_nb_info;
tmp_next = nb_left->next_nb_info;

nb_left->prev_nb_info = nb_right->prev_nb_info;
nb_left->next_nb_info = nb_right->next_nb_info;

nb_right->prev_nb_info = tmp_prev;
nb_right->next_nb_info = tmp_next;

left++;
nb_left = nb_left->next_nb_info;

right--;
nb_right = nb_right->prev_nb_info;
}

if (i_left < left-1)
quick_sort(left0, nb_left->prev_nb_info, i_left, left-1);

if (right+1 < i_right)
quick_sort(nb_right->next_nb_info, right0, right+1, i_right);
}

int main(){
struct nb_info nb_info[MAX_IDX];
struct nb_info *nb;
int i;

/* 配列の初期化 */

quick_sort(&nb_info[0], &nb_info[5], 0, MAX_IDX-1);

}
字数制限のため　main()関数内の　結果表示部は省きました。
これで　私の頭の中はイメージできますでしょうか　汗
いろいろ間違えているのでしょうね；；