Rubyによる選択ソートの理解

この記事はもともとは書かれていたJulie Kent でHoneybadger Developer Blog .
このポストでは、Rubyで選択ソートアルゴリズムを実装する方法を歩きます.選択ソートは、適所比較ソートアルゴリズムです.これは、ソートされたアイテムは、元のものと同じストレージを占有することを意味します.我々がこれ以上行く前に、データ集合が小さい(すなわち、10 - 20の要素)ない限り、選択ソーティングアルゴリズムが慣例で一般的に使用されないことに注意するのは重要です.しかし、それを学び、理解するための素晴らしいスターターアルゴリズムは、自転車の前に三輪車に乗る方法を学習に似ています.実装はジョブインタビューのためのコーディングチャレンジに現れるかもしれません、あるいは、セレクションソートのようなアルゴリズムがなぜ大きなデータセットで非常に実用的でないか説明するよう頼まれるかもしれません.選択ソートは通常、このシリーズで見た最初のアルゴリズムであるバブルソートを上書きします.
高いレベルでは、選択ソートは2つの部分に配列を分割します.開始時に、ソートされたセクションは空です、そして、unsortedされた部分は要素の全てを含みます.選択ソートは2つのループを利用します外側のループはn回繰り返します.nは配列の要素数です.私たちはすぐに最初の要素に“min index”を設定し、別のループを使用して要素を比較します.
これが続くのが難しいならば、心配しないでください!次の実例を見ます.

一歩一歩

次の要素を持つ配列から始めましょう[10, 30, 27, 7, 33, 15, 40, 50]反復1:最小数を見つける
この場合、最小数は7 , それで、我々は始めにそれを置いて、動きます10 どこに7 です.現在の配列は次のようになります.[7, 30, 27, 10, 33, 15, 40, 50]反復2 :次の最小数を見つける
インデックス位置1の要素から始まる(覚えておいて、配列は0からインデックスされます)、次の最小要素を見つけます
この場合は10. 移動10 配列と移動の2番目の位置に30 どこに10 です.結果の配列は以下の通りです.[7, 10, 27, 30, 33, 15, 40, 50]ここから、私たちの配列が完全にソートされるまで、この正確なプロセスを続けます.以下に、次の繰り返しの後に結果の配列を見ることができます.
反復3 :[7, 10, 15, 30, 33, 27, 40, 50]反復4[7, 10, 15, 27, 33, 30, 40, 50]反復5[7, 10, 15, 27, 30, 33, 40, 50]ビンゴ!我々はソートされます!
あなたがより視覚的な学習者であるならば、選択ソートがどのように配列の[]
Photo credit

Rubyの実装

Rubyで書かれた選択ソート関数を示します.

def selection_sort(array)
  n = array.length - 1
  n.times do |i|
    min_index = i
    for j in (i + 1)..n
      min_index = j if array[j] < array[min_index]
    end
    array[i], array[min_index] = array[min_index], array[i] if min_index != i
  end
  puts array
end

これがどのように働くか見てみましょう.
最初に、我々はセットn 要素の数に等しい.配列が0 - indexedされるので、我々は1を引く必要があります.
次に、我々の外側ループを作成しますn 回.

min_index = i

ここで、最小インデックスを1番目の位置の要素に設定します.

for j in (i + 1)..n

次に、我々は内側のループを作成します.この行は、「第2の要素の第nの要素の要素については、次のことを行う」と言います.あなたがよく知らないならば.. 演算子は、開始点から終了点までの範囲を包括的に作成します.例えば、1..10 1から10までの範囲を含みます.

min_index = j if array[j] < array[min_index]

このループの中でmin_index を返します.min_index .

array[i], array[min_index] = array[min_index], array[i] if min_index != i

我々の内部のループの外で、我々は現在かどうかを見ますmin_index はi . これが本当であるならば、我々は我々の要素をシャッフルする必要があります.セットarray[i] to array[min_index] and array[min_index] to array[i] . ここでは、我々が我々の例でしたように「スワップ」を実行しています.
最後に、一度我々が終了すると、我々は現在ソートされている配列を出力!

すべてをまとめる

これが私の完全なプログラムです

def selection_sort(array)
  n = array.length - 1
  n.times do |i|
    min_index = i
    for j in (i + 1)..n
      min_index = j if array[j] < array[min_index]
    end
    array[i], array[min_index] = array[min_index], array[i] if min_index != i
  end
  puts array
end

array = [10, 30, 27, 7, 33, 15, 40, 50]

selection_sort(array)

走るruby ruby-selection-sort.rb 端末から次の出力を行います.

7
10
15
27
30
33
40
50

クール!

選択ソートが非効率である理由の理解

アルゴリズムの効率を測定する1つの方法は、「ビッグ- O記法」を見ることですこれはアルゴリズムが比較できるように最悪のパフォーマンスを表します.例えば、O(1)のBig - Oを持つアルゴリズムは、“N”の要素の数が増加するにつれて最悪の実行時間が一定であることを意味しますが、O(N)のBIG - O表記を持つアルゴリズムは、Nが大きくなると、最悪の実行時間が直線的に増加することを意味します.これは、100個の要素を持つ配列を持ち、o ( n )とo ( 1 )のソートアルゴリズムを選択する必要がある場合、O ( 1 )がO ( 100 )を確実に打つので、O ( 1 )アルゴリズムを選択します.
バブルソートのように、選択ソートは入れ子になったループのためにO(n ^ 2)の最悪の場合と平均的な複雑さを持ちます.これは元素数が増加すると効率が劇的に減少することを意味する.

ラッピング

すべてのものは、選択ソートはまだコーディングアルゴリズムにポップアップすることが興味深いアルゴリズムです.または、選択ソート機能を与えられるかもしれません、そして、ビッグO記法が何であるか、そして、理由を尋ねました.うまくいけば、この記事の例では、いずれかのシナリオに取り組む準備ができます.