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

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

ただいまの
回答率

90.46%

  • Ruby

    9691questions

    Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

  • アルゴリズム

    516questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

  • ソート

    86questions

    複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

選択ソートについて教えてください

解決済

回答 2

投稿

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

poroporo_335

score 9

選択ソートについて、以下のようなコードを書いてみました。

def selection_sort(numbers)

  (numbers.length-1).times do |i|
    min = i
    k = i + 1

      while k < (numbers.length) 
        if numbers[k] < numbers[min]
          min = k
        end
      k = k + 1
      end


    numbers[min] , numbers[i] = numbers[i] , numbers[min]
        i = i + 1
  end
    p numbers
end

selection_sort([10,2,12,7,16,8,13,1])


出力自体は問題ないのですが、いくつか疑問が残っていますので、質問させていただきたいと思います。

変数iminkについて

配列 [10,2,12,7,16,8,13,1]に対して、
ソート前の状態ではiが10、kが2、minは1が当てはまり、繰り返されるたびに、配列の先頭が+1されていくと言う認識で正しいでしょうか?

上記が正しいと仮定して、min = iとすることでiと比較した最小値が取得できるのは何故でしょうか?

while文について

while k < (numbers.length) 
        if numbers[k] < numbers[min]
          min = k
        end
      k = k + 1
      end


の部分も、本当はtimesメソッドを使ってみたかったのですが、うまくいきませんでした。
どのようにするのが適切なのでしょうか。

ご教示のほど、よろしくお願いいたします。

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 2

checkベストアンサー

0

配列 [10,2,12,7,16,8,13,1]に対して、
ソート前の状態ではiが10、kが2、minは1が当てはまり、繰り返されるたびに、配列の先頭が+1されていくと言う認識で正しいでしょうか?

i,k,minは要素番号を示すので、「iは0, k2 1, 1回目のソート処理のminは7」が正しいです。
配列の先頭が+1というのはまあ合っているでしょう。

上記が正しいと仮定して、min = iとすることでiと比較した最小値が取得できるのは何故でしょうか?

何もない状態で比較することはできないので、仮に先頭の位置を最小と置いているだけです。
iと比較しているわけではなく、minkを使って比較してます。

本当はtimesメソッドを使ってみたかったのですが、うまくいきませんでした。
どのようにするのが適切なのでしょうか。

timesは0からN-1までの値でループするメソッドなので、そのまま使うと正しく処理できません。
どうしてもtimesがいいということであれば、0〜配列.length-kとなるようにtimesを使い、
kの値にループ値を加算するようにすれば良いかと思います。

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/11/06 21:52

    要素番号とは、配列のインデックス番号のことでよろしいでしょうか。
    その場合、1回目の処理では、iが[0]、kが[1]、minが[7]と認識していましたが、違ったでしょうか。
    iと比較してと言うのは早計すぎたかもしれませんが、minやkを使って「min[7]」と言う最小値をどのようにして探せるのかが不思議でなりません。そう言うものだと割り切るしかないのかもしれませんが・・
    timesについてのご指摘もありがとうございます。
    色々試してみて、eachの方がスマートに感じたのでそちらを選択しようかと思います。

    キャンセル

  • 2018/11/07 11:14

    > 要素番号とは、配列のインデックス番号のことでよろしいでしょうか。
    合ってます。

    > その場合、1回目の処理では、iが[0]、kが[1]、minが[7]と認識していましたが、違ったでしょうか。
    合ってます。
    私の回答のkが間違ってました。

    > minやkを使って「min[7]」と言う最小値をどのようにして探せるのかが不思議でなりません。
    紙に配列を書いてプログラムの流れを追うとわかりやすいのですが、
    未確定の左端を最小値の仮の要素番号(min)とし、そこから右側を順に見ていきます(k)。
    minの値とkの値を比較して、kの値が小さければminを更新してからまた右側を見ていきます。
    配列の最後まで比較し終わったとき、minの要素番号が最小値の要素番号になります。

    キャンセル

  • 2018/11/07 22:13

    とてもわかりやすい解説ありがとうございます。
    ようやく流れが理解できた気がします。

    実際の数字で追ってみました。
    [3,9,6,1,2]とう言う配列があったとして、
    1回目の処理では、3がi、仮のmin・9がkとなり、minとkを比較し
    3<9(kの方が大きい)ので、k+1で右隣の6がkになる

    3<6(kの方が大きい)ので、k+1で右隣の2がkになる

    3>2(kの方が小さい)ので、2が仮minに代入される

    2>1(kの方が小さい)ので、1が仮minに代入される

    ここで、kが配列の個数に達したため処理完了。
    minは1となり、3(i)と交換する。
    交換したら、iに1+され、2回目の処理は9が仮のminとなって同じ要領で繰り返し処理が行われる。

    という解釈に辿りつきましたm(_ _)m

    キャンセル

  • 2018/11/08 10:50

    概ね合っているように思います。

    キャンセル

0

ソート前の状態ではiが10、kが2、minは1が当てはまり、

「iが10」は「iが1」の書き間違いでしょうか?
ただし、Rubyの配列は0始まりなので、全部1つずれてますが。

繰り返されるたびに、配列の先頭が+1されていくと言う認識で正しいでしょうか? 

これはちょっと意味がわかりません。

自分で書いたプログラムの意味がわからないのでしたら、もう一度、よく考えながらプログラムを書き直しましょう。

どのようにするのが適切なのでしょうか。 

プログラムをあまり書き換えない範囲で、少し書き直してみました。インデントも正しく付けなおし。

def selection_sort(numbers)
  numbers.each_index do |i|
    min = i
    ((i+1)...numbers.length).each do |k|
      if numbers[k] < numbers[min]
        min = k
      end
    end
    numbers[min] , numbers[i] = numbers[i] , numbers[min]
  end
  p numbers #これはメソッドの外に出した方が良い
end

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/11/06 21:06

    eachを使った修正回答ありがとうございます。
    仰せの通り、自分で書いたプログラムの意味を細かく把握していないので、じっくり考えてみます。

    キャンセル

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

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

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

  • Ruby

    9691questions

    Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

  • アルゴリズム

    516questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

  • ソート

    86questions

    複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。