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

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

A 回答 (2件)

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



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

並べ換えの問題
 http://www.cs.u-gakugei.ac.jp/~miyadera/Educatio …
    • good
    • 0
    • good
    • 0

このQ&Aに関連する人気のQ&A

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

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

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

Qオフロードバイクのタイヤについて

XR250モタードの購入を考えているのですが、オフロードも走りに行きたいと思っています。オフロードツーリングに行くときにだけ、オフロードタイヤのホイールに履き替えて使うということはできるのでしょうか?

Aベストアンサー

こん**わ

 まず回答としては「可能です」

 ただ、モタードホイールは17インチ
 オフロードホイールは前21インチ後ろ18インチとなっているので
 タイヤの大きさが変わります。
 となるとホイールだけ変えただけではスピードメーターや距離計が変わってしまいます。
 メーターギヤーも交換が必要でしょう。

 また、リヤスプロケの大きさも変わるとチェーンも交換しないと行けなくなります。
 結構手間なので両方したいのならオフロードモデルをお薦めします。

 がんばってください

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ベストアンサー

<オフロードバイクはテクニックが無ければ乗るのは危険でしょうか?>
全くそんな事ありません。
どこまでを「テクニックと言うか?」になってしまいますが、、、
オフ車はオフ車なりの「乗り方」みたいなモノがあるにはあります。

ですが、これまでに過去にオフ車に全く乗って無かったけど、、、ってヒトでも最初は「ん?何じゃ?」って思う事はあるけど、それとて30分も乗れば「ああ、こんな感じなんだな」ってスグに慣れてしまうはずです。

<オフ車の素人がオフロードバイクのテクニックが皆無な状態で、オンもオフも走るのは危険でしょうか?>
んな事はありません。
危険な乗り方すれば、オフでもオンでも危険なだけです。
いきなりオフ車でオフロードは危険もありますが、それとて少しづつ慣れていけば問題無いです。

<乗っていくにつれて分かってくるものなのでしょうか?>
そうですね、そんなもんですよ。。。

<オフロードを乗っている方々はどこかで習っているのでしょうか?>
そういう方もいるでしょう。
しかし、普通に乗る場合には特段の練習なんか必要ありません。
「オフロード車の乗り方」みたいな本を一読して実践出来ることからやってみるだけでも十分ですよ。

一般に市販されてるバイクで特別な訓練やテクニックを必要としてるバイクなんかありません。

どんなタイプのバイクだろうと、普通に(街乗り程度)使うのであれば訓練やテクニックなんて必要無いんです。
(普通に乗る事が出来るって事が条件ですけどね)

ただ、そのバイク固有に特化した何かに合わせた使い方をするのであれば、それなりのテクニックは必要です。

そのバイクの持っている特徴=性能=を最大限に出せる場所に於いて、そのバイクの能力を引き出すのであれば、そこはテクニックがモノを言う世界なんです。。。

例えば、オフ車を普通の街乗りで使う場合であれば、テクニックなんか必要ありませんが、このオフ車を林道や瓦礫道へ持って行って、このオフ車が持つ能力を最大限まで引き出すような走行をするなら、オフ車特有のテクニックが必要なだけです。
これはSSだとて同じ事です。

そして、オフ車は比較的誰にでも扱い易いモノです。
(SSなんかと比べればの話ですけどね)

<オフロードバイクはテクニックが無ければ乗るのは危険でしょうか?>
全くそんな事ありません。
どこまでを「テクニックと言うか?」になってしまいますが、、、
オフ車はオフ車なりの「乗り方」みたいなモノがあるにはあります。

ですが、これまでに過去にオフ車に全く乗って無かったけど、、、ってヒトでも最初は「ん?何じゃ?」って思う事はあるけど、それとて30分も乗れば「ああ、こんな感じなんだな」ってスグに慣れてしまうはずです。

<オフ車の素人がオフロードバイクのテクニックが皆無な...続きを読む

Qバブルソートとセレクションソートの交換回数について

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

Aベストアンサー

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

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

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

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

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

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

Qオフロードバイクの街乗りメリット

オフロードバイクの街乗りメリット

オフロードバイクを街乗りメインにして乗るのは邪道ですか?やはり林道メインでしょうか。

また街乗りでオフロードバイクに乗ることでオンロードバイクにはない、メリットはありますか?

ヤマハセローがとても気になっています。
よろしくお願いします。

Aベストアンサー

街乗りこそ オフ車です 街中は コンクリートジャングルですから
車体がスリム=すり抜けが楽 ステアの位置が高い=すり抜け時四輪のミラー擦らない
ステアの切れ角が大きい=わき道にすぐ入れる 
減速比が低い=スタートダッシュが良い 全般に着座位置が高い=前方視界が良い 
爆窃団の標的になり辛い 万が一コケても レバーやミラー程度で済む

 オマケとして 多少傷があったほうが オフ車ぽく見える

こんなトコデスガ

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ベストアンサー

オンもオフも混ぜて10数台乗り継いでる人間です。

オフロード車で走る「メリット」もありますが、あえてオフロード者に乗る人は「魅力」に魅かれている場合も多いです。


・軽量な車体でとり回しが楽
例えば250ccですとオンロードバイクが140kg~に対して
オフロードバイクはせいぜい重くても~120kgぐらいです。
住宅街を抜けての通勤や買い物に行くときは本当に便利です。
後、オンロードバイクのような高回転でパワーを出すものと違い
低回転から力強く足を運んでくれるのでキビキビ走ってくれます
それに全体的に見て燃費のいいバイクも多いです。


・高い目線
ミニバン人気の一つ「車体からの視野の広さ」と同じ部分があります
オンロードバイクのように前傾姿勢になりにくいので目線が高く遠くまで見えます。
街中をレーサーレプリカで走ると首が疲れます(笑


・週末のツーリングにもってこい
気合を入れて峠に通うような人でなければオフロード車の走行性能で十分です
尚且つ標準キャリアのバイクが多くて箱をつけてても「ツーリングライダー」として様になります
オンロードバイクはツアラーでないと、なかなか「箱付き」は不恰好ですから…。


・車体の整備性のよさ、頑丈な作り
単気筒のバイクが多く、パーツ点数の少なさからDIY整備が非常に楽です
ある程度バラす前提があること(泥が色んなところに入り込みますので)から
基本的には各部パーツのはずし方も複雑でなく、簡単なものが多いです
また、林道などでコケることも前提に作ってますので道路で緊急回避でコケたとしても
大体の場合はそのままなにごともないようにエンジンかけて走ってけれます。
オンロード車はすぐハンドル曲がったとかタンクヘコんだとか外装に色々気を使いますから…。

・二人乗りが楽
意外なメリットで、私の場合はこれがありました。
一つ前の型のKLXに乗っていたのですが、シートがちょうどよい弾力で
それなりに幅広、かといってまたを開くわけでもないので
女の子を乗せて「このバイクが一番いい」といわれました
アメリカンは密着できず背もたれ便りになるのが逆に怖かったそうです。


私がオフロードに乗っていて感じたメリットはこんなところです。

質問主さんのように「なんで?」と感じる方やカッコ悪いという方も多く
私も当初はそう感じていたのですが、次第にはまっていきました
無骨なデザインやタフで頼れる相棒という感じで、とても信頼がおけます。
オフロード好きって、本当にバイク好きそう…と、自分に酔いしれてた時期もありました(笑

オンもオフも混ぜて10数台乗り継いでる人間です。

オフロード車で走る「メリット」もありますが、あえてオフロード者に乗る人は「魅力」に魅かれている場合も多いです。


・軽量な車体でとり回しが楽
例えば250ccですとオンロードバイクが140kg~に対して
オフロードバイクはせいぜい重くても~120kgぐらいです。
住宅街を抜けての通勤や買い物に行くときは本当に便利です。
後、オンロードバイクのような高回転でパワーを出すものと違い
低回転から力強く足を運んでくれるのでキビキビ走ってくれます...続きを読む

Qクイックソートのアルゴリズムについて

(1)クイックソートが使われるのは実際にはどのような場面なのでしょうか?メインメモリで使われていると聞きましたが‥
(2)クイックソートが一番早いと聞きましたがコームソートやバブルソートなどは使われないのでしょうか?
(3)マージソートはどのような局面で使われるのでしょうか?

Aベストアンサー

 #1です。再登場。

>具体的にはどんなデータを扱っているのでしょうか?
 SQLのエンジンです。フリーで出してるんです。
 どんなデータが来るか予測できないので、ソート方式の選定には苦労した記憶があります。
 ちなみに、自分なりに実験した結果、俺が使ってるp-マージソートは、クイックソートと比べても遅延は少ししかないみたいです。

QKSR-(2)のオフロードタイヤ

KSR-(2)に合うオフロードタイヤはあるのでしょうか??
会社の先輩に、『オフロードコースを走ろう!』と誘われたのですが
純正タイヤは、オンロード・・・
『オフロードタイヤはあるのかな??』と言う疑問に・・・
ご存知のかた、アドバイスよろしくお願いします。

Aベストアンサー

オフロードタイヤをはいたKSRを見た事があるので、あると思いますよ。

公道不可でもいいならミニモト用のモトクロタイヤという手もあります。
http://www.inoac.co.jp/irc/mc/products/jr_kids_mx.html
他にも各社から出ています。
カタログサイズでは入りそうだけど、ブロックハイトがあるから、実際はどうかな?
あんまり勧めないけどね。
バイク屋さんにある販売店用のカタログにはいろいろ載っているので、
なじみの店で見せてもらうといいですよ。

参考URL:http://www.inoac.co.jp/irc/mc/products/jr_kids_mx.html

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;

と同じ意味になる。

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

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


人気Q&Aランキング

おすすめ情報