こんにちわ。
構造体配列のリストを ポインタのつなぎ変えによるクイックソートで
以下のようなソートをしたいのですが、悩んでおります。
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をたどっていくことでちゃんと目的の値の昇順になっている
というのを実現したいのですが、ポインタのつなぎ変えか何かが
間違っているようで うまいことできていません。
どなたかご教授いただけますでしょうか。
申し訳ありませんが、よろしウお願いいたします。
A 回答 (7件)
- 最新から表示
- 回答順に表示
No.7
- 回答日時:
一般論です。
平均オーダーはクイックソート、マージソートともO(n*log(n))で同等ですが、係数はクイックソートの方が小さく、一般に倍ほど速いといいます。ただ最悪時はクイックソートがO(n^2)と悪化するのに対してマージソートは最悪でもO(n*log(n))で安心できます。またクイックソートは評価値が同じ項目の順序が安定しない性質があるので、複数の評価値で順にソートする場合には向きません。
こういった特徴もあり、Javaのライブラリなどでは、基本型はクイックソート、オブジェクト型はマージソートをベースとするアルゴリズムを使っています。リンクリストならマージソートの方がお勧めできるかと思います。
No.6
- 回答日時:
#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
- 回答日時:
クイックソートは本質的にシーケンシャルアクセスしか使わないので, 双方向リストに適用することも (一応は) 可能ですよ>#3.
ただ「同じ値もかなり含まれると思う」というのはちょっと不安. ピボットとして「先頭と中間と末尾の値の平均」を使ってるけど, 「ソートしようとしている部分」がすべて同じ値だった場合, 当然これらはすべて同じ値であり, したがってピボットの値も同じになります. ところが, そのような場合クイックソートの性能は最悪になる可能性があります.
「どんなデータが来てもそれなりに効率的に実行できる」という意味ではマージソートの方が安心できるかなぁ.
No.4
- 回答日時:
> あ、また、どうしても 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
- 回答日時:
双方向リストの場合配列の添え字でアクセスできないので
基本的にクイックソートはあんまり使わないと思います。
マージソートでは駄目なのでしょうか?
この回答への補足
ご回答 ありがとうございますm(_ _)m
実際には、かなり大量なデータをソートしなければならなくなるのですが、また、同じ値もかなり含まれると思うのですが、この場合、効率的には クイックソートとマージソート どちらのほうがよいのでしょうか?
もともとクイックソートを選んだのは あまり知識がなかったためでもあり、効率的に変わらず、下記に示しましたことが実現できるのであればマージソートにしたいと思います。これからまた勉強しなければなりませんが(^^;
あの、ちなみに、この一番の問題となっております、構造体配列のindexと、
構造体内の変数の値の組み合わせは変えたくなく、構造体内のprev, next変数の値の変更によるポインタの繋ぎ変えだけで ソートを実現したいのですが、
そのための注意事項や 実現の仕方について 少し具体的にアドバイスいただくことはできますでしょうか(>_<)
もしトンチンカンなことを言っていたらすみません;
No.2
- 回答日時:
どうしてもポインタのリンクでやりたいのでしたら、無視してくれてかまいませんが、単に間接参照したのではダメなのですか?
こんな感じ。なんかあれば補足してください
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
- 回答日時:
>ポインタのつなぎ変えによるクイックソート
っていうのが今ひとつうまくイメージできませんが、
何はともあれ、ソースコード全体を見せてください。
そうすれば、何かが見えてくるかもしれません。
この回答への補足
こちらも さっそくの回答 ありがとうございます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()関数内の 結果表示部は省きました。
これで 私の頭の中はイメージできますでしょうか 汗
いろいろ間違えているのでしょうね;;
あ、すみません、pだのheadだのは さきほど奮闘中に このようにポインタの繋ぎ変え?でソートを行う場合 headを用意していないと 先頭がどこか分からなくなる というような記述をネットで目にしまして 試行錯誤中のため書いてしましましたが、
p = &head;
p->next_nb_info = left0;
p = left0;
は 無視していただいてかまいません;;
必要であれば、そのようにコメントしていただいてもかまいません;;
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
- C言語・C++・C# プログラミング c言語 4 2023/03/07 01:05
- C言語・C++・C# C言語初心者 構造体 課題について 2 2023/03/10 19:48
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- C言語・C++・C# leetcode21 1 2022/04/21 11:53
- C言語・C++・C# C言語 leetcode21 Merge Two Sorted Lists 2 2022/04/24 19:35
- C言語・C++・C# C言語初心者 ポインタについて、お助けください、、 2 2023/03/15 23:50
- Excel(エクセル) VBAで組み合わせ算出やCOUNTIFSの処理を高速化したいです。 4 2022/04/07 02:38
- Java javaでのプログラム(配列)について質問です. 2 2022/10/14 22:27
関連するカテゴリからQ&Aを探す
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
「指定されたキャストは有効で...
-
C言語での引数の省略方法
-
数字列を3桁ごとにカンマで区切...
-
複数桁10進数の*桁目だけを抽出...
-
C言語 エラーの原因がわからな...
-
【C++】関数ポインタの使い方
-
(int *)の意味
-
C言語のサイコロシミュレート
-
ラップ関数とはどんなものですか?
-
c++でテンプレートのコードでわ...
-
#define _CRT_SECURE_NO_WARNIN...
-
c言語の配列を使ってサイコロを...
-
(マルチスレッド)_beginthrea...
-
実数の整数部,小数部の取得
-
入力を待たずにstdinの監視をし...
-
C言語で、数値の桁数を求めるに...
-
「{ } で囲むだけ」は正しい?
-
構造体の勉強中です 合計点の高...
-
比較回数と交換回数表示について
-
課題でつまってます・・・
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
「指定されたキャストは有効で...
-
C言語での引数の省略方法
-
#define _CRT_SECURE_NO_WARNIN...
-
複数桁10進数の*桁目だけを抽出...
-
へんな現象
-
【C++】関数ポインタの使い方
-
C言語 エラーの原因がわからな...
-
if と配列の組み合わせ
-
C言語での奇数の和
-
C言語 配列と関数の練習問題
-
ラップ関数とはどんなものですか?
-
(int *)の意味
-
C言語
-
実数の整数部,小数部の取得
-
足して100になるような乱数のア...
-
卒業研究でよく分からないとこ...
-
数字列を3桁ごとにカンマで区切...
-
c言語
-
std::set<int> で、ある値が何...
-
比較回数と交換回数表示について
おすすめ情報