初めまして、インプルの山形です。
今回はプログラミングを学習していれば一度はその名を耳にしたことがあるような有名なアルゴリズムをJavaScriptの実装を通して学習したのでそれを記事にまとめたいと思います。
はじめに
エンジニアの方、エンジニアではないけどプログラミングを趣味や勉強として学習中の方、皆さんはプログラミングでどんな時に楽しい、あるいはおもしろいと思えるでしょうか？
アプリを作成することに楽しさを見出す方、プログラミングを学ぶ過程そのものに楽しさを見出す方、コードを書くことそれ自身が面白いと思える方、人それぞれ色々な答えがあると思います。
私は「ロジックを考えて実装している」時に時間をわすれて楽しさを感じます。
そんな私が、「ロジックを考える楽しさを味わえ、同時に実装力も鍛えることができる題材はないか？」と考えた結果、アルゴリズムを勉強するという答えに辿り着き、本記事を書くに至りました
今回は選択ソートアリゴリズムを取り上げていこうと思います。
選択ソートアルゴリズムとは
選択ソートアリゴリズムとは何か？まずはコードで学習する前にその定義から見てみましょう。
以下wikipediaより引用。
選択ソートは配列の整列されていない部分から最小値または最大値を持つ要素を探して、その値ソートのアルゴリズムの一つ。 配列から最小値を探し、配列の先頭要素と入れ替えていくことで並べ替える。
https://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E%E3%82%BD%E3%83%BC%E3%83%88
これだけだとすこしむずかしいですね。具体例を交えてもう少し噛み砕いて解説してみます。
例えば、[3,4,2,1]という配列があり、これを昇順に並べ替えたいとします。この時、まず、この配列の中から線型探査(要はしらみつぶしにということです)によって最小値を取得します。この場合「１」がそれに該当します。「1」をみつけたらそれを配列の先頭と入れ替えます。今回の場合は「3」と入れ替えます。
最初のソートのこの時点で、[1,4,2,3]の順になり、配列の添字「０」は整列ずみとみなします。次に、配列の添字「1」から探索対象とし同じ操作を繰り返します。したがって、[4,2,3]から最小値を探索、「2」が見つかるので「4」と交換。配列の添字「１」が整列ずみとなり、[1,2,4,3]となります。
この操作を配列の要素数分繰り返して、ソートするのが選択ソートアルゴリズムとなります。
選択ソートアルゴリズムをJavaScritpで実装する
選択ソートのアルゴリズムが何かわかったところで、JavaScriptで実装してみます。与えられた配列をsort関数を使用せずに、昇順で並び替えるアルゴリズムを実装してみます。
const selectionSort = (array, start=0) => {
if(start === array.length){
return array; // - ①
}
let min = start; // - ②
for(let i = start + 1; i < array.length; i++){
if(array[min] > array[i]) min = i; // - ②
}
[array[start], array[min]] = [array[min], array[start]]; // - ③
return selectionSort(array, start+1)
}
const testCase = [2,43,8,19,0,23,67,24,67];
const result = selectionSort(testCase);
console.log(result);
// [0, 2, 8, 19, 23,24, 43, 67, 67]
今回は二重ループを使用せずに再帰関数を使用して実装してみました。ポイントは3つあります。
- 再帰関数による実装は、必ずどこかで再帰を止めなければなりません。今回は探索の開始点を関数の実行と同時にstartという変数で渡して、startを配列の要素数分インクリメントしていきます。startが配列の要素数に達したら、呼び出し元に返却することで再帰関数の実行から離脱できます。(①)
- 最小値の添字をstartで初期化します。forループで全探索し、array[min]がarray[i]より大きければminをiで更新します(②、③)
- forのループが終了したら、分割代入で交換します。
ちなみにご覧の通りこの実装は破壊的な実装をしているので、元配列に変更を加えたくない場合はsliceメソッドやスプレッド演算子でコピーを作成し、参照による共有を防ぐ必要があります。
終わりに
あくまで、上記の実装は一例です！
この実装以外にも他に様々なやり方があると思いますので、気になる方はご自身で考えてみたり、調べてみるとさらに選択ソートアルゴリズムに対する理解が深まるかもしれません！
(余談ですが、別な実装方法での実装を考えるということも非常に面白く、勉強になるので私自身もよくやります！）
ここまでご覧いただきありがとうございました！
参考
キタミ式イラストIT塾 基本情報技術者 令和05年 (https://gihyo.jp/book/2022/978-4-297-13186-9)
選択ソートアルゴリズム解説(https://www.codereading.com/algo_and_ds/algo/selection_sort.html)
wikipedia (https://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E%E3%82%BD%E3%83%BC%E3%83%88)