【アルゴリズムの勉強】Rubyで挿入ソートを書いてみる
挿入ソートとは
挿入ソート(インサーションソート)は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。
挿入ソートを高速化したソート法として、シェルソートが知られている。
Rubyで実装
arr = [4, 20, 6, 10, 2, 15, 60, 9, 25, 12] number_of_elements = arr.count DESC, ASC = 1, 2 def insertion_sort(arr, number_of_elements, order) for i in 1..(number_of_elements - 1) target = arr[i] j = i if order == ASC while (j > 0) && (arr[j - 1] > target) arr[j] = arr[j - 1] j += -1 end elsif order == DESC while (j > 0) && (arr[j - 1] < target) arr[j] = arr[j - 1] j += -1 end end arr[j] = target end return arr end asc_sorted_arr = insertion_sort(arr, number_of_elements, ASC) p asc_sorted_arr # => [2, 4, 6, 9, 10, 12, 15, 20, 25, 60] desc_sorted_arr = insertion_sort(arr, number_of_elements, DESC) p desc_sorted_arr # => [60, 25, 20, 15, 12, 10, 9, 6, 4, 2]
【アルゴリズムの勉強】Rubyでバブルソートを書いてみる
バブルソートとは
ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。(単に交換法と言う場合もある)
Rubyで実装
arr = [4, 20, 6, 10, 2, 15, 60, 9, 25, 12] number_of_elements = arr.count # 降順, 昇順 ASC, DESC = 1, 2 def bubble_sort(arr, number_of_elements, order) for i in 1..(number_of_elements - 1) (number_of_elements - i).times{|j| if order == ASC if (arr[j] > arr[j + 1]) arr[j], arr[j + 1] = arr[j + 1], arr[j] end elsif order == DESC if (arr[j] < arr[j + 1]) arr[j], arr[j + 1] = arr[j + 1], arr[j] end end } end return arr end asc_sorted_arr = bubble_sort(arr, number_of_elements, ASC) p asc_sorted_arr # => [2, 4, 6, 9, 10, 12, 15, 20, 25, 60] desc_sorted_arr = bubble_sort(arr, number_of_elements, DESC) p desc_sorted_arr # => [60, 25, 20, 15, 12, 10, 9, 6, 4, 2]