質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.52%

  • C++

    3469questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

挿入ソート、バブルソート、選択ソートの手順が理解できません・・・

解決済

回答 3

投稿

  • 評価
  • クリップ 0
  • VIEW 420

k.keigo

score 32

挿入ソート、バブルソート、選択ソートの手順が理解できません。
どなたか教えてください。
ソースコードも提示していただけると幸いです。
よろしくお願いいたします。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • 退会済みユーザー

    2018/04/15 18:51

    複数のユーザーから「やってほしいことだけを記載した丸投げの質問」という意見がありました
    「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。

回答 3

+4

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/04/15 13:56

    手順はわかるのですが、ソースコードで表すのができません。
    よろしくお願いします。

    キャンセル

  • 2018/04/15 13:58

    ググればいくらでも出てくるので,課題等で急ぎであれば拾ってきてください。但し既に指摘されている通り,自分の力にしたいのであればある程度自分で考えないと意味がありません。

    キャンセル

  • 2018/04/15 13:59

    「手順」を計画した上で,それを「コード」に変換していく作業を「プログラミング」といいます。ここすっ飛ばしてたらプログラミングの力は身につかないですよ。

    キャンセル

  • 2018/04/15 14:00

    いきなりC言語のソースコードに落とし込むのが難しければ,

    〜の間ループ
     もし〜なら
      …する
     それ以外なら
      …する

    のような日本語を使って書いてからそれをC言語に変換してもいいし。

    キャンセル

  • 2018/04/15 17:14

    ↑の日本語でとりあえず書いてみるフェーズもできないのであれば,その状態を「手順はわかる」とは言いません。漠然とした概念を具体的な手順に書き出すことをやってみてから言ってください。

    キャンセル

checkベストアンサー

+1

こんにちは、

 まず初めに

他の方もおっしゃっていますが本当は自分である程度は考える必要があります。
もちろん人から教わるのも一つの勉強ですが、自分で考え理解することで初めて自分のものになります。
プログラミングは頭で考えるのが約80%、考えたことをコードに落とし込むのが約20%といわれています。
今回は、私が実際書いたコードを使って説明しますが、ひとつひとつ理解して進んでください。

1.挿入ソート

全てのデータの中で0番目からi番目までのうちi番目より大きい数字があったら,その2つを入れ替えるソートです。
最初はi = 0 その次はi = 1と増え それぞれ0からiまでの中で処理をするので、2重for文を使いましょう。

for(i = 0; i < MAX_NUMBER; i++){
    for(j = 0; j <= i; j++){
        if(data[i] < data[j]){
            tmp = data[i]; //2つのデータを入れ替える
            data[i] = data[j];
            data[j] = tmp; 
        }
    }
}


その都度、2つのデータを比べ右のほうが大きかったら、2つのデータを入れ替えます。
<サンプルコード>

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

#define MAX_NUMBER 10

int main(void){

    int data[MAX_NUMBER] = {8,4,5,7,9,1,13,2,15,6};
    int i,j;
    int tmp;
    for(i = 0; i < MAX_NUMBER; i++){
        for(j = 0; j <= i; j++){
            if(data[i] < data[j]){
                tmp = data[i];
                data[i] = data[j];
                data[j] = tmp;
            }
        }
    }
    for(i = 0; i < MAX_NUMBER; i++){
        printf("%d ",data[i]);
    }
    return 0;
}


2.バブルソート
3つの中では一番わかりやすいと思います。
隣り合った2つのデータを比べ、右のほうが大きかったら入れ替えます。
ここで、重要なのは一番右には最も大きいデータが来るということです。(最大となるものから右に寄る) 
そして、その次は、一番右以外でまた入れ替え作業をします。
データがN個のとき最初は,0番目からN - 1番目
その次は0番目からN - 2番目... となるのでここの2重for文は、

for(i = N - 1; i >= 0; i--){
    for(j = 0; j < i; j++){
    }
}


となります。実際の処理内容は先ほどと あまり変わらないので、説明は省略します。
<サンプルコード>

#include <stdio.h>

#define MAX_NUMBER 10

int main(void)
{
    int data[MAX_NUMBER] = {8,4,5,7,9,1,13,2,15,6};
    int i,j;
    int tmp;
    for(i = MAX_NUMBER - 1; i >= 0; i--){
        for(j = 0; j < i; j++){
            if(data[j] > data[j + 1]){
                tmp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = tmp;
            }
        }
    }
    for(i = 0; i < MAX_NUMBER; i++){
        printf("%d ",data[i]);
    }
    return 0;
}


3.選択ソート
これは説明も実際のコードも少し複雑になります。
最初は0番目だけ、その次は0番目から1番目...のように
0番目からi番目までの中で最小値を求め、その最小値を一番左にあるデータと入れ替えます。
ここで重要なのでは,最小値だけではなく、最小値がもともとあった場所を記憶する必要があるということです。

<サンプルコード>

#include <stdio.h>

#define MAX_NUMBER 10

int main(void)
{
    int data[MAX_NUMBER] = {8,4,5,7,9,1,13,2,15,6};
    int i,j;
    int tmp,tmp_posi;
    int tmp2;
    int position = 0;
    for(i = 0; i < MAX_NUMBER; i++){
        tmp = data[i];
        for(j = i; j < MAX_NUMBER; j++){
            if(tmp > data[j]){
                tmp = data[j];
                tmp_posi = j;
            }
        }
        tmp2 = data[position];
        data[position] = tmp;
        data[tmp_posi] = tmp2;
        position++;
    }
    for(i = 0; i < MAX_NUMBER; i++){
        printf("%d ",data[i]);
    }
    return 0;
}

 最後に

最初にも言いましたが、やはり自分で考えることが大切です。
2重for文の場合、中でどんな処理が行われているか最初はわからなくて混乱するかもしれません。
「i = 0 の時、jが0からMAX_NUMBERまで動くとこのような処理が行われる」など、
実際に、配列の番号のところに数字を代入して、確認することで理解が深まるでしょう。
地道な作業かもしれませんが、プログラミングを学ぶ上で大切なことだと思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/04/15 22:08 編集

    もし、間違えているところや気になった点があったら指摘してください。

    キャンセル

  • 2018/04/15 22:10

    他のソートだとシェルソートやクイックソートなどがありますが、やはり一番わかりやすいのは
    バブルソートかもしれません。

    キャンセル

  • 2018/04/15 22:10 編集

    ちなみに私が主に使っているソートは選択ソートです。

    キャンセル

  • 2018/04/16 07:23

    素朴な疑問ですが、選択ソートはそれほど速くありません。
    標準ライブラリのクイックソートはあえて使用しないということでしょうか?

    キャンセル

  • 2018/04/16 07:46 編集

    要素数に依りますよ。数十程度なら単純なソートの方がよっぽど速いし。
    とはいえ、わざわざ自前で書くことはないです僕は。

    # あと、安定なソートが条件ならクイックソートは使えない。

    キャンセル

  • 2018/04/16 08:55

    コメントをありがとうございます。
    要素数が少なく、反復して行われる場合選択ソートの方が速い可能性があるということですね。

    選択ソートも安定ソートではなかった記憶だったので…

    キャンセル

  • 2018/04/16 08:58

    > 選択ソートも安定ソートではなかった記憶だったので…
    実装次第じゃないかしら。
    最も小さい要素が複数あったとき、先頭寄りの要素を採用すれば安定すんじゃね?

    キャンセル

  • 2018/04/16 15:08

    [1,3,3,2]
    の時、3が入れ替わってしまうような…
    何かアルゴリズムを勘違いしてたら申し訳ありません。

    キャンセル

  • 2018/04/16 15:14

    あー...そかそか。
    「"配列をもいっこ用意して、そっちにソート結果を転記する"なら安定する」です。ゴメン。

    キャンセル

  • 2018/04/16 15:15

    if文で左が右より大きいときだけ入れ替える評価をしているので大丈夫だと思います。

    キャンセル

  • 2018/04/16 15:15

    ”単純選択”改め”単純挿入”ですね安定するのは。配列が対象では出番なさげ。

    キャンセル

  • 2018/04/16 15:17

    > if文で左が右より大きいときだけ...
    "バブルでのおはなし"ですよね?

    キャンセル

  • 2018/04/16 15:22

    if文で左が右より大きいときだけ...
    はいこれはバブルでのお話です。
    しかし、3つのどのソートをやっても最終結果は同じですよね?

    キャンセル

  • 2018/04/16 18:24

    挿入ソートとバブルソートが安定で、選択ソートは非安定かと。
    なので、選択ソートだけ結果が異なる可能性があります。

    比較演算子が定義されていればソートができるので、「イコール」でも「同じもの」とは限りません。
    そして、出現順序が重要となる場合、安定ソートを採用する必要があるという流れかと。

    キャンセル

  • 2018/04/30 09:53

    ありがとうございます

    キャンセル

+1

ググれば出てくるはずですが。
Qiita - 「ソート」を極める! 〜 なぜソートを学ぶのか 〜

また、当たり前の話ですが、理解した上で書かないとなんの得も無いということをお忘れなく。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.52%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • C++

    3469questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。