はじめまして。自学でCを学んでいるものです。いきなりですが、タイトルの通り、バブルソートとセレクションソート(直選択ソート)の交換回数が同じになるということは分かるのですが、その理由が分かりません。
何となくわかっているのですが、nや数式を用いて論理的に説明しろと言われると、お手上げです。自分の理解のためにもこの点はしっかりと押さえておきたいと思っています。
何卒よろしくお願いします。

このQ&Aに関連する最新のQ&A

A 回答 (3件)

> 比較回数はバブルソートと同様だが、要素の数が同じなら交換回数は常に同じという、安定性の高いアルゴリズムである。



これは、「バブルソートと選択ソートで交換回数は同じ」という意味ではありません。

「選択ソートでは、要素の数が同じなら、どんな入力データでも交換回数は同じ」という意味です。

たとえば、10要素の選択ソートなら、
「順序的に1番目にくるべき要素を、1番目と交換」
「順序的に2番目にくるべき要素を、2番目と交換」

「順序的に9番目にくるべき要素を、9番目と交換」
という流れになり、
どんな入力データであっても、10要素のソートなら交換回数は必ず9回になります。

一方、バブルソートの場合は、入力データの並びによって、交換回数が変わってきます。
    • good
    • 0

入力がある特定の並びについて「バブルソートと選択ソートの交換回数が同じ」であることはありえますが、


総じて見ると「バブルソートと選択ソートの交換回数の比較」では、基本的に「バブルソートの方が交換回数が多い」ことになります。
アルゴリズムの優劣を論じる状況においては「バブルソートと選択ソートの交換回数が同じ」などと言うことはありません。

参考: http://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E% …

> 多くのC言語のサイトを見てみると、交換回数が同じとしている

具体的に、どのサイトにそういう記述があるのか教えてくれませんか?

この回答への補足

必ずそうはならないということは分りました。


http://ew.hitachi-system.co.jp/w/E382BBE383ACE38 …
などです。要素の数が同じであることが条件となっているようです。その場合は交換回数は同じなのでしょうか。

補足日時:2009/05/26 23:00
    • good
    • 0

バブルソートと選択ソートでは、交換回数は同じではありません。

選択ソートの方が少なくなります。

バブルソートでは、二重ループの中で必要に応じて交換が行われますので、交換回数はO(n^2)です。

選択ソートでは、二重ループの中は「最小要素の探索」=「比較」のみで、交換はその外の一重ループレベルで行われます。交換回数はO(n)です。

一方、比較回数は、どちらも同じになります。

この回答への補足

回答ありがとうございます。このソートというものは、重複はなしです。

多くのC言語のサイトを見てみると、交換回数が同じとしているのは、また違った条件からなのでしょうか?
転倒数について考えるとその理由が出てくる、という記述のあるサイトがありましたが、それは関係あるでしょうか?

補足日時:2009/05/25 19:34
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q主語が複数でも比較級than any other 単数名詞?

問題集に

There are more violins than any other instrument in an orchestra.

という英文がありました。

主語がviolinsなので、instrumentも複数にしても良いのでしょうか?

Mt.Fuji is higher than any other mountain in Japan.のような例文では富士が単数だから1対1で比較する必要があり、ゆえにmountainは単数だという説明を目にしたことがあります。

今回の英文の、主語は複数形で比較対象は単数形を理屈でどう説明できるのでしょうか?

Aベストアンサー

>Eagles soar higher than any other birds. 

これは、birdsと言う表現で、eagles以外の鳥全てを含んだ意味になっているからです。eaglesと、その他の鳥を全部いっしょくたにして比較しています。

>There are more violins than 【any other instruments】 in an orchestra.

と言うのは、やはりおかしくて、any other instrumentが正しいのです。
なぜなら、バイオリンとその他の楽器全ての合計数を比較しているわけではないからです。比べているのは、バイオリンと例えばトランペット、例えばトロンボーンと言うように比べているわけですから、あくまで一つ一つの楽器の種類です。
もし、There are more violins than 【any other instruments】 in an orchestra.と言ってしまえば、トランペット4、トロンボーン5、シンバル3、小太鼓2のようにバイオリン以外の楽器の数を合計し、その総合計よりもバイオリンの数が多いと言うことになります。

>Eagles soar higher than any other birds. 

これは、birdsと言う表現で、eagles以外の鳥全てを含んだ意味になっているからです。eaglesと、その他の鳥を全部いっしょくたにして比較しています。

>There are more violins than 【any other instruments】 in an orchestra.

と言うのは、やはりおかしくて、any other instrumentが正しいのです。
なぜなら、バイオリンとその他の楽器全ての合計数を比較しているわけではないからです。比べているのは、バイオリンと例えばトランペット、例えばトロン...続きを読む

Qバブルソートとクイックソート

まだソートについて勉強し始めたばかりですが
バブルソートは対象の総数が増えるとそれに伴い比較回数は増加するのに対し
クイックソートはそれほど増加しないのはなぜでしょうか??
検索してみてもプログラムが書いてあってよくわからないので...

根本的なところなのでしょうがどなたか教えてください!

Aベストアンサー

では「計算量」というキーワードも追加して検索してください。
また、計算量を表わすのに使われる「オーダー」「ランダウの漸近記法」についても調べてみてください。

おおざっぱに言うと

まじめに比較すれば、
一つ目と残りn-1個の比較
2つ目とそれ以降のn-2個の比較
...
と、要素数nの二乗に比例した回数の比較必要です。これがバブルソートの計算量です。

これを、大きいもの方と小さい方の半分に分けてそれぞれを並び変えれば、
1つの並び換えが(n/2)の二乗= 1/4 * nの2乗
それが大と小の2回で * 2
合わせて 1/4 * nの2乗 * 2
= 1/2 * nの2乗
とバブルソートの半分になります。その半分のものを更に半分に...とやっていくと、最後には n * log2 n に比例する値になります。 これが、クイックソートの計算量です。(正確には平均ですが)

細かい点は省略しているので、最初に書いたような検索の結果や、「アルゴリズム」について詳しく書かれた専門書などを読んでください。

Q比較級、最上級 A diamond is more precious than any other

比較級、最上級
A diamond is more precious than any other jewel.

A diamond is the で始まるように書き換えるとどうなりますか?

Aベストアンサー

学校文法の正解としては

A diamond is the most precious jewel of all. か
A diamond is the most precious of all the jewels. か。

Mt. Fuji is higher than any other mountain in Japan.
Mt. Fuji is the highest mountain in Japan.
のように最上級では名詞をつけて書き換えることが多いです。

Q挿入ソートとバブルソート

挿入ソートとバブルソートについて教えてください。どのようなアルゴリズムでソートされるのでしょうか?

Aベストアンサー

下記のページが参考になりませんか。

C言語によるアルゴリズム(コメント付き)http://www.sra.co.jp/people/miyata/algorithm/

並べ換えの問題
 http://www.cs.u-gakugei.ac.jp/~miyadera/Education/Lecture/ElecBook2/ptech17.htm

Q比較級 than SV について

こんにちは。比較級を勉強しているのですが、以下の文で
thanの後がSVになる場合とそうでない場合の違いがわかりません。
どういう時に than SV になるのか教えていただけると助かります。

〈thanの後がSVにならない場合〉
She walks more slowly than other girls.
He can speak English better than me.
Tom got to the station earlier than his friends.

〈thanの後がSVになる場合〉
He read the book more carefully than I did.
My brother studies much longer than I do.
Do you study harder than he does?

よろしくお願いします!

Aベストアンサー

こちらでいろいろな考えが出てきています。

http://oshiete.goo.ne.jp/qa/1654320.html

単純にいうと,接続詞か前置詞か。
さらに接続詞なら省略も含まれる。
さらには,接続詞と言っても従属接続詞的な場合もあれば等位接続詞
的な場合もあり,関係代名詞的なものもある。

than the record のように接続詞的には説明できず,
句構造(前置詞)としか考えられないものが出てくる。

He is taller than me.
は長い間,日本では誤りだとされてきました。
he is tall と I am tall と比べるんだから I という主格。

現実には He is taller than I. という英語は避けられ,
He is taller than I am.
とするか,
He is taller than me. とする。

than me というのはネイティブにとっては極めて普通の英語です。

He likes her better than he likes me. の省略が
He likes her better than me. だという意見もよく見ますが,
He likes her better than I like her. も
He likes her better than me. と言えます。

まさしく,日本語の「彼は私より彼女の方が好きだ」という日本語で
「私より」が「彼は」との比較か,「彼女を」との比較か
あいまいになるのと同じ。
than me というのはそういう表現です。

上であげた質問の回答にもありますが,than ~は先に表現ありき,
文法の説明は後付け。

こちらでいろいろな考えが出てきています。

http://oshiete.goo.ne.jp/qa/1654320.html

単純にいうと,接続詞か前置詞か。
さらに接続詞なら省略も含まれる。
さらには,接続詞と言っても従属接続詞的な場合もあれば等位接続詞
的な場合もあり,関係代名詞的なものもある。

than the record のように接続詞的には説明できず,
句構造(前置詞)としか考えられないものが出てくる。

He is taller than me.
は長い間,日本では誤りだとされてきました。
he is tall と I am tall と比べるんだから I という主格...続きを読む

Q双方向リストのバブルソートについて

双方向リストをバブルソートを用いてソートしたいです。
下記がプログラム(一部)ですが、ソートした後にリスト表示すると
無限ループに陥ります。
どこがいけないのでしょうか。

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

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

void insert_head(struct cell **head, int num){
struct cell *p, *p1;

p = *head;
p1 = make_cell();
*head = p1;
p1->data = num;
p1->next = p;

if(p1->next != (struct cell *)NULL){
p1->next = p;
p->prev = p1;
}
}

void print_list(struct cell *head){
struct cell *p;

p = head;
printf("data = \n");
while(p != (struct cell *)NULL){
printf("%d\n", p->data);
p = p->next;
}
}

void sort_list(struct cell **head){
struct cell *p, *p2;
int i, n;

n = 0;
p = *head;
while(p->next != (struct cell *)NULL){
p = p->next;
n++;
}

for(i = 0, p = *head; i < n-2; i++){
if(p->data > p->next->data){
if(p == *head){
*head = p->next;
}else{
p->prev->next = p->next;
}
p2 = p->next;
p->next = p->next->next;
p->next->next = p;
p->next->next->prev = p;
p->next->prev = p->prev;
p->prev = p2;
}else
p = p->next;
}
}

int main(void){
struct cell *head = (struct cell *)NULL;
int n;

while(1){
printf("1:Insert head 2:Insert tail 3:Delete 4:List 5:Sort 6:Exit\n");
scanf("%d", &n);
switch(n){
case 1:
printf("num = ");
scanf("%d", &n);
insert_head(&head, n);
break;
case 2:
printf("num = ");
scanf("%d", &n);
insert_tail(&head, n);
break;
case 3:
printf("num = ");
scanf("%d", &n);
delete_cell(&head, n);
break;
case 4:
print_list(head);
break;
case 5:
sort_list(&head);
break;
case 6:
return 0;
break;
}
}
}

双方向リストをバブルソートを用いてソートしたいです。
下記がプログラム(一部)ですが、ソートした後にリスト表示すると
無限ループに陥ります。
どこがいけないのでしょうか。

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

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

void insert_head(struct cell **head, int num){
struct cell *p, *p1;

p = *head;
p1 = make_cell();
*head = p1;
p1->data = num;
p1->next = p;

if(p1->next != (struct cell *)NULL){
p1->next = p;
...続きを読む

Aベストアンサー

p2 = p->next;
p->next = p->next->next;
p->next->next = p;
p->next->next->prev = p;
p->next->prev = p->prev;
p->prev = p2;

の部分で

p->next->next = p;

の後に

p->next->next->prev = p;

をやると、これは

p->prev = p;

と同じ意味になる。

「自分の前は自分」と言う状態になり、この状態で、もう一度上記のルーチンを通ると「自分の次は自分」と言う状況が出来上がる。

表示ルーチンは「自分の次が、次」とやっているのだから、リストが「自分の次は自分」になってれば、無限ループするのが当たり前。

ソートルーチンで、2つの要素を入れ替えする場合は、以下に示した[1]~[6]の6つのポインタを書き換えないといけない筈。

pの---[1]-->p---[3]-->p2---[5]-->p2の
前 <--[2]--- <--[4]---  <--[6]---次

質問者さんのプログラムでは「5つしか書き換えてない」ので、それだけで「バグっている」のが明白。

以上を踏まえると、pとp2の入れ替えは、以下のようになる。

p2=p->next;
if (*head!=p) p->prev->next = p2; /*pに前が居る場合だけ、 [1]の付け替え*/
if (p2->next) p2->next->prev = p; /*p2に次が居る場合だけ、[6]の付け替え*/
p->next = p2->next;         /*               [3]の付け替え*/
if (*head!=p) p2->prev = p->prev; /*pに前が居る場合だけ、 [4]の付け替え*/
p2->next = p;             /*               [5]の付け替え*/
p->prev = p2              /*               [2]の付け替え*/
if (*head==p) *head = p2;      /*pがheadだったら、p2が新しいheadになる*/

p2 = p->next;
p->next = p->next->next;
p->next->next = p;
p->next->next->prev = p;
p->next->prev = p->prev;
p->prev = p2;

の部分で

p->next->next = p;

の後に

p->next->next->prev = p;

をやると、これは

p->prev = p;

と同じ意味になる。

「自分の前は自分」と言う状態になり、この状態で、もう一度上記のルーチンを通ると「自分の次は自分」と言う状況が出来上がる。

表示ルーチンは「自分の次が、次」とやっているのだから、リストが「自分の次は自分」になってれば、無限ループするのが当た...続きを読む

Qmore than ? better than ?

いつもお世話になっております。
中学生に聞かれているんですが、
I like baseball better than any other sport.
という文はOK でしょうか?わたしは、better than の部分をmore than にすべきではないかと思うのですが、説明ができません・・・。
more than は可能だと思うのですが、better than でもOKですか?
宜しくご指導ください。

Aベストアンサー

手元に「詳説 レクシス プラネットボード 103人のネイティブスピーカーに聞く生きた英文法・語法」という本があります。その中にお尋ねと同じ質問をして得られた解答と分析があります。それによると、「使用率はあまり変わら」ず、betterはmoreに比べて「やや口語である人もいる」とあり、「学習者はいずれを用いてもよいだろう」としています。ちなみに、英米の差はほとんどないという結果が表から読み取れます。

Qバブルソート:ポインタで並び替えについて。

今C言語の研修中で、バブルソートのプログラムをくんでいます。
それで、以下のように配列で入れ替えではなく、ポインタで入れ替えをしたいのですが、
 dt+i = dt+i+1;
 dt+i+1 = dt2;
で、
 invalid lvalue in assignment
というエラーが出てしまいます。
書き方がまちがっているんでしょうか?
参考書やHPも探してみたのですが、探し方が悪いのかどうにもわかりません。
研修中なので、調べるのも勉強だとは思うのですが、お手上げで・・・・・・
情けないですが、教えていただけると嬉しいです。
/** ソート処理 **/
static int SORT_PROC(void)
{
  int i,m;
  syouhin_typ *dt2;

  /** バブルソートでソート処理 **/
  for(m=0; m<i_cnt-1; m++){
    for(i=0; i<i_cnt-1;i++){
      if(strncmp((dt+i)->code,(dt+i+1)->code,sizeof(dt->code)) >= 0){
         dt2 = dt+i;
         dt+i = dt+i+1;
         dt+i+1 = dt2;
      }
    }
  }
}

ちなみにdtはグローバル変数で、
typedef struct{
  char code[5]; /** 商品コード **/
  char uriage[5]; /** 売上数 **/
}syouhin_typ;

/** グローバル変数 **/
syouhin_typ *dt; /** 商品 **/

としてあります。

今C言語の研修中で、バブルソートのプログラムをくんでいます。
それで、以下のように配列で入れ替えではなく、ポインタで入れ替えをしたいのですが、
 dt+i = dt+i+1;
 dt+i+1 = dt2;
で、
 invalid lvalue in assignment
というエラーが出てしまいます。
書き方がまちがっているんでしょうか?
参考書やHPも探してみたのですが、探し方が悪いのかどうにもわかりません。
研修中なので、調べるのも勉強だとは思うのですが、お手上げで・・・・・・
情けないですが、教えていただけると嬉しいです...続きを読む

Aベストアンサー

a-kuma> ANSI の規格が無かった頃ならいざ知らず、今どきの普通のコンパイラは構造体の
a-kuma> 代入を許してくれますぜ。

どうも古い頭で済みません。
が、

sora8181> *dt2 = *(dt+i);
sora8181> だとコンパイルの時にコアダンプしてしまうので、
sora8181> dt2 = (dt+i);
sora8181> でコンパイルが通りました。

実行時ならいざしらず、コンパイル時にエラーとなるのは、sora8181さんのコンパイラが
この記述を許していない証拠です。*を落としたのでは意味が変わってしまいますから、
これでコンパイルが通っても困ります。

Qthan any other か than any others か?

問題集の中に、
I like this song better than any others.
This book was more useful than any other.
という2つの文がのっていました。どっちが正しいのでしょうか?
I like this song better than any other song.
ならわかるのですが。

Aベストアンサー

回答者No.1です.お礼を拝見しました.

はい,両方とも使われる…ということですから,両方とも正しいと言ってよいでしょう.

QC言語の構造体にてバブルソートが上手くいきません‥

C言語の構造体にてバブルソートが上手くいきません‥

初めて質問致します。

以下は、構造体で、身長順にバブルソートを行うソース文ですが、
結果表示が、最下部に示したように、
5つのレコードのうち1つが消えてしまい、
残った4つのレコードのうちの1つが重複されて表示されてしまいます。
これが、なかなか解決できません‥。

既に結構調べており、また、早く解決できないといけないこともあり、
すみませんが、回答の形式でお願いできますと大変幸いです。
何卒よろしくお願い致します。


#include<stdio.h>
#include<string.h>

typedef struct kojin {
char name[21];
int length;
int weight;
}KOJIN;

int main(void)
{
int i, c, j;
char buf[4];
KOJIN data[10];
KOJIN *d;

printf(

C言語の構造体にてバブルソートが上手くいきません‥

初めて質問致します。

以下は、構造体で、身長順にバブルソートを行うソース文ですが、
結果表示が、最下部に示したように、
5つのレコードのうち1つが消えてしまい、
残った4つのレコードのうちの1つが重複されて表示されてしまいます。
これが、なかなか解決できません‥。

既に結構調べており、また、早く解決できないといけないこともあり、
すみませんが、回答の形式でお願いできますと大変幸いです。
何卒よろしくお願い致します。


#i...続きを読む

Aベストアンサー

>for(i=0;i<10;i++) {
>d = &data[i];

最終的には、 dには &data[9] 、つまり、data[9]へのポインタが入っているわけです。
そして、そのまま

>*d= data[i];
>data[i]= data[j];
>data[j]= *d;
を実行したら
*dはdata[9]になりますから

data[9]= data[i];
data[i]= data[j];
data[j]= data[9];

と同じ事、となります。
一応、data[i]とdata[j]との入れ替えにはなりますが、同時にdata[i]がdata[9]へコピーされてしまい、もとあったdata[9]の内容が失われます。
最終的に、最後の入れ替えが発生したときのdata[i]と同じ値がdata[9]に入っているとこになります。

対策は、この KOJIN *d を使わないことです
KOJIN temp ;
としておいて

temp= data[i];
data[i]= data[j];
data[j]= temp;

とします。

ところで、これ、バブルソートじゃないですよ。
単純ソートというアルゴリズムになってます。
アルゴリズムの参考書等をもう一度よく確認してください。

>for(i=0;i<10;i++) {
>d = &data[i];

最終的には、 dには &data[9] 、つまり、data[9]へのポインタが入っているわけです。
そして、そのまま

>*d= data[i];
>data[i]= data[j];
>data[j]= *d;
を実行したら
*dはdata[9]になりますから

data[9]= data[i];
data[i]= data[j];
data[j]= data[9];

と同じ事、となります。
一応、data[i]とdata[j]との入れ替えにはなりますが、同時にdata[i]がdata[9]へコピーされてしまい、もとあったdata[9]の内容が失われます。
最終的に、最後の入れ替えが発生したときのdata[...続きを読む


人気Q&Aランキング

おすすめ情報