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

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

新規登録して質問してみよう
ただいま回答率
85.50%
Ruby

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

アルゴリズム

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

ソート

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

Q&A

解決済

2回答

1478閲覧

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

poroporo_335

総合スコア15

Ruby

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

アルゴリズム

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

ソート

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

0グッド

0クリップ

投稿2018/11/05 14:29

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

ruby

1def selection_sort(numbers) 2 3 (numbers.length-1).times do |i| 4 min = i 5 k = i + 1 6 7 while k < (numbers.length) 8 if numbers[k] < numbers[min] 9 min = k 10 end 11 k = k + 1 12 end 13 14 15 numbers[min] , numbers[i] = numbers[i] , numbers[min] 16 i = i + 1 17 end 18 p numbers 19end 20 21selection_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メソッドを使ってみたかったのですが、うまくいきませんでした。
どのようにするのが適切なのでしょうか。

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

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

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

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

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

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

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

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

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

Ruby

1def selection_sort(numbers) 2 numbers.each_index do |i| 3 min = i 4 ((i+1)...numbers.length).each do |k| 5 if numbers[k] < numbers[min] 6 min = k 7 end 8 end 9 numbers[min] , numbers[i] = numbers[i] , numbers[min] 10 end 11 p numbers #これはメソッドの外に出した方が良い 12end

投稿2018/11/05 15:01

編集2018/11/05 15:11
otn

総合スコア84423

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

poroporo_335

2018/11/06 12:06

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

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と比較しているわけではなく、min, kを使って比較してます。

本当はtimesメソッドを使ってみたかったのですが、うまくいきませんでした。

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

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

投稿2018/11/05 14:58

編集2018/11/07 02:09
dice142

総合スコア5158

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

poroporo_335

2018/11/06 12:52

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

2018/11/07 02:14

> 要素番号とは、配列のインデックス番号のことでよろしいでしょうか。 合ってます。 > その場合、1回目の処理では、iが[0]、kが[1]、minが[7]と認識していましたが、違ったでしょうか。 合ってます。 私の回答のkが間違ってました。 > minやkを使って「min[7]」と言う最小値をどのようにして探せるのかが不思議でなりません。 紙に配列を書いてプログラムの流れを追うとわかりやすいのですが、 未確定の左端を最小値の仮の要素番号(min)とし、そこから右側を順に見ていきます(k)。 minの値とkの値を比較して、kの値が小さければminを更新してからまた右側を見ていきます。 配列の最後まで比較し終わったとき、minの要素番号が最小値の要素番号になります。
poroporo_335

2018/11/07 13: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
dice142

2018/11/08 01:50

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問