この記事では、バブルソートとクイックソートの2つのアルゴリズムを用いて、配列をソートする流れをGPTに解説してもらいながら紹介します。
バブルソート
配列内の隣り合う要素を比較して、大小関係が逆であれば入れ替えることを繰り返すことで、配列を昇順または降順にソートする。
このアルゴリズムは、大きい値（または小さい値）が「泡」のように配列の右端（または左端）に浮かび上がることから、バブルソート（Bubble Sort）と呼ばれている。
実装
コメント付きで実装してもらう。
number_array = [3, 5, 9, 7, 1]
# 配列の長さを取得
array_length = number_array.length
# 配列の要素を比較して並べ替える
(array_length - 1).times do |i|
(array_length - 1 - i).times do |j|
# 隣り合う要素を比較して、前の要素が後ろの要素より大きい場合に入れ替える
if number_array[j] > number_array[j + 1]
number_array[j], number_array[j + 1] = number_array[j + 1], number_array[j]
end
end
end
puts number_array.inspect
疑問点
疑問点を挙げていきます。
timesメソッドってなんだっけ
Integerクラスに定義されたメソッドで、指定した回数だけブロック内のコードを繰り返し実行する。
ブロック内では、現在の反復回数をブロック変数として取得することもできる。
なぜ外側のループは、配列の長さ-1にするの？
最後の要素が自動的に正しい位置に配置されるから。
1回目のループの流れを例に説明する。
- 外側のループの1回目が始まります。
- 内側のループが実行され、以下の比較・入れ替えが行われます。
- number_array[0]（3）とnumber_array[1]（5）を比較。入れ替えなし。
- number_array[1]（5）とnumber_array[2]（9）を比較。入れ替えなし。
- number_array[2]（9）とnumber_array[3]（7）を比較。9が7より大きいため、入れ替えが行われ、配列は[3, 5, 7, 9, 1]になります。
- number_array[3]（9）とnumber_array[4]（1）を比較。9が1より大きいため、入れ替えが行われ、配列は[3, 5, 7, 1, 9]になります。
- 内側のループが終了します。最も大きい値（9）が配列の右端に移動して確定しました。
- 外側のループの1回目が終了します。
外側のループが1回終了するたびに、最も大きい未確定の値が配列の右端に確定していく。
このプロセスを繰り返し、最後の要素については他の要素がすでに正しい位置に配置されているため、自動的に正しい位置になる。
.inspectってなに？
オブジェクトの内容を文字列形式で返すメソッド。オブジェクトの内容をデバッグ目的で人間が読める形で出力する際に便利。
クイックソート
Tony Hoareによって1960年に開発された高速な比較ソートアルゴリズム。
分割統治法（Divide and Conquer）というアプローチを使用しており、再帰的に問題を解決できる。
実装
まずはコメント付きで実装してもらう。
def quicksort(array)
# 配列の長さが1以下の場合、ソート済みとして配列を返す
return array if array.length <= 1
# 配列の中央要素をピボットインデックスとして取得
pivot_index = (array.length / 2).to_i
# ピボットインデックスに対応する値をピボット値として取得
pivot_value = array[pivot_index]
# 配列からピボット値を削除
array.delete_at(pivot_index)
# ピボット値より小さい値を格納する配列
less = []
# ピボット値より大きい値を格納する配列
greater = []
# 配列の各要素に対して以下の処理を行う
array.each do |value|
# 要素がピボット値以下の場合、less配列に追加
if value <= pivot_value
less << value
# 要素がピボット値より大きい場合、greater配列に追加
else
greater << value
end
end
# less配列とgreater配列を再帰的にクイックソートし、ピボット値を挟んで結合して返す
return quicksort(less) + [pivot_value] + quicksort(greater)
end
# ソート対象の配列を定義
number_array = [3, 5, 9, 7, 1]
# quicksort関数で配列をソートし、結果を格納
sorted_array = quicksort(number_array)
# ソート済みの配列を出力
puts "Sorted array: #{sorted_array}"
疑問点
疑問点を挙げていきます。
そもそも処理の流れがよくわからん
なので実際に処理の流れを説明してもらう。
- quicksort
([3, 5, 9, 7, 1])が呼び出されます。 - 配列の長さが1より大きいため、処理を続行します。
- ピボットインデックスは
(5 / 2).to_i = 2となります。したがって、ピボット値は 9 です。 - 配列からピボット値 9 を削除し、配列は
[3, 5, 7, 1]になります。 - 配列の各要素をピボット値と比較して、
less = [3, 5, 7, 1]、greater = []となります。 - less 配列と greater 配列を再帰的にクイックソートします。
- quicksort
([3, 5, 7, 1])が呼び出されます。 - ピボットインデックスは 2、ピボット値は 7 です。
- 配列からピボット値 7 を削除し、配列は
[3, 5, 1]になります。 - 配列の各要素をピボット値と比較して、
less = [3, 5, 1]、greater = []となります。 - less 配列と greater 配列を再帰的にクイックソートします。
- quicksort
([3, 5, 1])が呼び出されます。 - ピボットインデックスは 1、ピボット値は 5 です。
- 配列からピボット値 5 を削除し、配列は
[3, 1]になります。 - 配列の各要素をピボット値と比較して、
less = [3, 1]、greater = []となります。 - less 配列と greater 配列を再帰的にクイックソートします。
- quicksort
([3, 1])が呼び出されます。 - ピボットインデックスは 1、ピボット値は 1 です。
- 配列からピボット値 1 を削除し、配列は
[3]になります。 - 配列の各要素をピボット値と比較して、
less = []、greater = [3]となります。 - less 配列と greater 配列を再帰的にクイックソートします。
- quicksort([]) は空の配列を返す。
- quicksort([3]) は要素数が1のため、そのまま [3] を返す。
- 結果の配列を結合します。
[] + [1] + [3]となり、[1, 3]が返されます。 - 結果の配列を結合します。
[1, 3] + [5] + []となり、[1, 3, 5]が返されます。 - 結果の配列を結合します。
[1, 3, 5] + [7] + []となり、[1, 3, 5, 7]が返されます。 - 結果の配列を結合します。[1, 3, 5, 7] + [9] + [] となり、
[1, 3, 5, 7, 9]が返されます。
quicksortの中でquicksortを使い、それを最終的に結合させていると。
メソッドの中でメソッド使っていいの？
問題ない。コードをモジュール化することで再利用性と可読性が向上する。
これは再帰と呼ばれる手法でアルゴリズムの実装を簡潔かつ効果的に行える。
適切なエラー処理や終了条件をただしく設定しないと、無限ループやスタックオーバーフローの問題が発生してしまう。
ピボットってなに？
クイックソートアルゴリズムにおいて、配列を分割する際に選択される基準となる要素のこと。
ピボットが配列の中央値に近いほど、クイックソートの性能は向上する。
選択するピボットは中央じゃなきゃだめなの？
必ずしもそうではない。どの戦略が最適化は問題の性質やデータの特性による。
中央要素をピボットとして選択することは、一般的には効率的な方法だが、他の戦略でもよい。
例えば、以下のよう
- 配列の最初の要素をピボットとして選択
- 配列の最後の要素をピボットとして選択
- 配列の中央要素をピボットとして選択（この質問で言及されている方法）
- 配列からランダムに要素を選択してピボットとする
- 配列の複数の要素から中央値を計算し、ピボットとして選択（メディアン・オブ・メディアン法）
おわりに
以上、クイックソートとバブルソートを使ったソートのやり方でした。