EN
JP
KRSelection Sortとは？JavaScriptで選択ソートを実装する方法を解説
Selection Sortは、ソートアルゴリズムの基本としてよく学ばれる手法の一つです。日本語では選択ソートと呼ばれ、未ソート部分の中から最小値を探し、その値を現在の位置と交換することで配列を少しずつ整列させていきます。JavaScriptでアルゴリズムを学ぶとき、Selection Sortは最小値の探索、インデックス管理、交換処理、二重ループといった基礎的な考え方を理解するのに適しています。Bubble Sortと同じく実装は比較的シンプルですが、値の動き方や考え方は異なるため、複数のソートアルゴリズムを比較して学ぶうえでも重要です。
Selection Sortは、平均ケースや最悪ケースでO(n^2)の時間計算量になるため、大規模データを扱う実務処理には向いていません。実務では、多くの場合JavaScript標準のArray.prototype.sort()を使う方が現実的です。しかし、Selection Sortを学ぶことで、配列のどの範囲がすでに整列済みで、どの範囲がまだ未ソートなのかを意識できるようになります。また、最小値のインデックスを記録して最後に交換するという流れは、配列操作の理解を深めるのに役立ちます。本記事では、Selection Sortの仕組み、JavaScriptでの実装方法、swap関数を使った整理、計算量、Bubble Sortとの違い、学習時のポイントまで詳しく解説します。
1. Selection Sortとは？
Selection Sortとは、配列の中から最小値を選び、その値を先頭から順番に配置していくソートアルゴリズムです。昇順に並べる場合、最初は配列全体の中から最小値を探し、その値を先頭の要素と交換します。次に、2番目以降の未ソート部分から最小値を探し、2番目の要素と交換します。この処理を繰り返すことで、左側から順番にソート済みの領域が広がり、最終的に配列全体が整列されます。処理の流れが明確で、初心者でも手順を追いやすい点がSelection Sortの特徴です。
Selection Sortでは、各ステップで「今の位置に入るべき値を選ぶ」という考え方をします。Bubble Sortのように隣接する要素を何度も交換するのではなく、未ソート部分を一度走査して最小値の位置を見つけ、必要であれば現在位置と交換します。そのため、比較回数は多いものの、交換回数は比較的少なくなります。実務で大量データを高速に処理する用途には向きませんが、最小値探索やインデックス操作を学ぶうえでは非常に分かりやすいアルゴリズムです。
1.1 選択ソートの考え方
選択ソートでは、「現在の位置に最もふさわしい値を未ソート部分から選ぶ」という考え方をします。たとえば、昇順に並べたい場合、配列の先頭には最小値が来るべきです。そのため、まず配列全体を確認して最小値を探し、その値を先頭に置きます。次に、先頭はすでに正しい位置にあると考え、2番目以降の範囲から次に小さい値を探します。このように、処理が進むたびに左側のソート済み領域が一つずつ増えていきます。
この考え方を理解するには、ソート済み領域と未ソート領域を分けて見ることが重要です。最初は配列全体が未ソート領域ですが、1回の処理が終わるたびに、左側に確定済みの値が増えていきます。Selection Sortは、各ステップで最小値を選んで固定していくため、配列のどの部分がすでに整列されているのかを意識しやすいアルゴリズムです。JavaScriptで実装するときも、外側のループが現在位置を表し、内側のループが未ソート領域から最小値を探す役割を持つと考えると理解しやすくなります。
1.2 入力と出力
Selection Sortの入力は、並び替えたい配列です。最も基本的な例では、数値の配列を受け取り、小さい順または大きい順に並び替えます。たとえば、[5, 3, 8, 1]という配列を昇順に並べると、結果は[1, 3, 5, 8]になります。学習段階では、まず数値配列の昇順ソートから始めるとよいでしょう。数値の比較は分かりやすく、最小値を探す処理も直感的に理解しやすいためです。
Selection Sortの考え方は、数値配列だけでなく、文字列配列やオブジェクト配列にも応用できます。たとえば、商品一覧を価格順に並べる場合は価格を比較し、ユーザー一覧を年齢順に並べる場合は年齢を比較します。ただし、実務でオブジェクト配列を並び替える場合は、標準のsort()メソッドを使う方が一般的です。Selection Sortは、入力された配列に対してどのように最小値を選び、どのように整列済み領域を広げていくのかを学ぶための基本アルゴリズムとして理解するとよいでしょう。
1.3 Selection Sortの特徴
Selection Sortの特徴は、実装が比較的簡単で、処理の流れを追いやすいことです。未ソート部分から最小値を探し、現在位置と交換するという単純な手順を繰り返すため、アルゴリズムの構造が明確です。また、各ステップで最小値のインデックスを記録するため、配列の値そのものだけでなく、インデックスを管理する練習にもなります。JavaScriptで配列操作を学ぶうえで、Selection Sortは基礎力を高める良い題材です。
一方で、Selection Sortは比較回数が多いという欠点があります。配列がすでに整列されていても、未ソート領域から最小値を探すために比較を続ける必要があります。そのため、最良ケースでも平均ケースでも最悪ケースでも、基本的にはO(n^2)の時間計算量になります。ただし、交換回数は最大でもn - 1回程度であり、Bubble Sortより少なくなることが多いです。このように、Selection Sortは交換回数が少ない一方で比較回数が多いという特徴を持っています。
2. Selection Sortの動作手順
Selection Sortは、配列の左側から順番に正しい値を確定していくアルゴリズムです。各ステップでは、現在位置を基準にして、その位置以降の未ソート部分から最小値を探します。最小値の位置が分かったら、現在位置の要素と交換します。これを配列の最後近くまで繰り返すことで、配列全体が昇順に整列されます。処理の流れは非常に規則的であり、外側のループと内側のループの役割を理解しやすいのが特徴です。
たとえば、[5, 3, 8, 1]を昇順に並べる場合、最初に配列全体から最小値を探します。この配列では1が最小値なので、先頭の5と交換します。すると配列は[1, 3, 8, 5]になります。次に、2番目以降の[3, 8, 5]から最小値を探します。この範囲では3が最小値で、すでに正しい位置にあるため交換は不要です。次に[8, 5]から5を見つけて8と交換します。このように、Selection Sortでは処理が進むたびに左側の値が確定していきます。
2.1 未ソート領域から最小値を探す
Selection Sortでは、まず未ソート領域の中から最小値を探します。JavaScriptで実装する場合、外側のループで現在位置をiとして管理し、内側のループでi + 1以降の要素を確認します。このとき、最小値そのものを保存するのではなく、最小値のインデックスをminIndexとして記録するのがポイントです。インデックスを記録しておけば、探索が終わったあとで現在位置と最小値の位置を簡単に交換できます。
最小値を探す処理では、result[j] < result[minIndex]のように現在の候補と比較します。もしより小さい値が見つかれば、minIndexをその位置に更新します。この処理を未ソート領域の最後まで続けることで、その範囲の最小値の位置が分かります。Selection Sortでは、この最小値探索が各ステップの中心になります。値だけを見るのではなく、「どの位置に最小値があるのか」を把握することが重要です。
2.2 現在位置と交換する
未ソート領域から最小値のインデックスを見つけたら、現在位置の要素と交換します。たとえば、現在位置がiで、最小値の位置がminIndexなら、result[i]とresult[minIndex]を入れ替えます。この交換によって、現在位置にはその時点で未ソート領域の中で最も小さい値が配置されます。つまり、その位置の値は確定し、次のステップでは比較対象から外すことができます。
ただし、現在位置がすでに最小値である場合、交換する必要はありません。minIndex !== iという条件を入れておけば、不要な交換を避けられます。これは小さな工夫ですが、コードの意図を明確にするうえでも役立ちます。Selection Sortでは、比較回数を大きく減らすことは難しいですが、交換回数はもともと少なく、必要なときだけ交換する構造になっています。この点は、隣接要素を何度も交換するBubble Sortとの違いでもあります。
2.3 ソート済み領域を広げる
Selection Sortでは、1回の処理が終わるたびに、現在位置の値が確定します。最初の処理では先頭の値が確定し、次の処理では2番目の値が確定します。このように、左側から順番にソート済み領域が広がっていきます。外側のループのiは、現在確定させようとしている位置を表しており、iより左側はすでに整列済みと考えることができます。
この考え方を理解すると、Selection Sortのループ範囲が分かりやすくなります。内側のループは、すでに確定した左側の要素を見る必要がないため、i + 1から始めます。未ソート領域だけを対象にして最小値を探し、見つけた値を現在位置に置くことで、ソート済み領域が一つ広がります。Selection Sortを学ぶときは、配列全体を見るのではなく、「左側は確定済み、右側は未ソート」という視点で追うと理解しやすくなります。
3. JavaScriptでSelection Sortを実装する
JavaScriptでSelection Sortを実装するには、二重ループを使います。外側のループは現在位置を表し、内側のループはその位置以降の未ソート領域から最小値を探すために使います。最小値の位置をminIndexとして保存し、内側のループが終わったあとで現在位置と交換します。この流れを繰り返すことで、配列全体を昇順に並び替えることができます。
実装するときは、元の配列を直接変更するかどうかも考える必要があります。学習用のコードでは元配列をそのまま変更しても構いませんが、実務では元データを保持したい場面が多いため、コピーを作ってから処理する方が安全です。この記事では、[...numbers]でコピーを作成し、そのコピーに対してSelection Sortを実行します。こうすることで、関数の外にある元の配列を壊さず、ソート済みの新しい配列を返せます。
3.1 基本実装
以下は、数値配列を昇順に並べるSelection Sortの基本実装です。まずresultに元配列のコピーを作り、外側のループで現在位置iを決めます。次に、minIndexを現在位置で初期化し、内側のループでi + 1以降の要素を確認します。より小さい値が見つかった場合は、minIndexを更新します。内側のループが終わった時点で、minIndexには未ソート領域の最小値の位置が入っています。
最後に、minIndexが現在位置iと異なる場合だけ交換します。この条件を入れることで、すでに現在位置が最小値である場合の不要な交換を避けられます。Selection Sortの実装では、値を直接保存するのではなく、最小値のインデックスを保存する点が重要です。これにより、探索後に配列内の要素を正しく入れ替えることができます。
function selectionSort(numbers) { const result = [...numbers]; for (let i = 0; i < result.length - 1; i++) { let minIndex = i; for (let j = i + 1; j < result.length; j++) { if (result[j] < result[minIndex]) { minIndex = j; } } if (minIndex !== i) { [result[i], result[minIndex]] = [result[minIndex], result[i]]; } } return result;}console.log(selectionSort([5, 3, 8, 1])); // [1, 3, 5, 8]
3.2 swap関数を使う
Selection Sortでは、現在位置と最小値の位置を交換する処理が必要になります。この交換処理を毎回コード内に直接書いても問題ありませんが、swap関数として切り出すとコードの意図が分かりやすくなります。swap(array, i, j)のような関数を用意しておけば、指定した配列のi番目とj番目の要素を入れ替える処理として再利用できます。Bubble SortやQuick Sortなど、他のアルゴリズムでも同じ交換処理を使えるため、学習用コードの整理にも役立ちます。
swap関数を使うと、Selection Sort本体では「最小値の位置を探す処理」と「見つけた位置と現在位置を交換する処理」が分かれます。これにより、コードを読んだときに役割が明確になります。JavaScriptでは分割代入を使うことで、交換処理を短く書けます。ただし、初心者が仕組みを理解する段階では、一時変数を使った交換方法も確認しておくとよいでしょう。どちらの書き方でも、2つの値を安全に入れ替えるという目的は同じです。
function swap(array, i, j) { [array[i], array[j]] = [array[j], array[i]];}function selectionSort(numbers) { const result = [...numbers]; for (let i = 0; i < result.length - 1; i++) { let minIndex = i; for (let j = i + 1; j < result.length; j++) { if (result[j] < result[minIndex]) { minIndex = j; } } if (minIndex !== i) { swap(result, i, minIndex); } } return result;}
3.3 降順にする方法
Selection Sortを降順にしたい場合は、最小値ではなく最大値を探します。昇順では未ソート領域の中から最小値を選び、現在位置に配置しました。降順では、大きい値を前に置きたいので、未ソート領域の中から最大値を探します。そのため、minIndexではなくmaxIndexという変数を使い、比較条件をresult[j] > result[maxIndex]に変更します。基本構造は昇順の場合とほとんど同じです。
降順のSelection Sortを実装すると、比較条件を変えるだけでソートの向きを切り替えられることが分かります。ランキングやスコア一覧、売上金額の高い順、人気数の多い順などでは、降順ソートがよく使われます。Selection Sortで降順を実装することは、実務で使うためというより、アルゴリズムの比較条件が並び順にどのように影響するのかを理解するために有効です。
function selectionSortDesc(numbers) { const result = [...numbers]; for (let i = 0; i < result.length - 1; i++) { let maxIndex = i; for (let j = i + 1; j < result.length; j++) { if (result[j] > result[maxIndex]) { maxIndex = j; } } if (maxIndex !== i) { [result[i], result[maxIndex]] = [result[maxIndex], result[i]]; } } return result;}
4. Selection Sortの計算量と特徴
Selection Sortの時間計算量は、最良ケース、平均ケース、最悪ケースのいずれも基本的にO(n^2)です。なぜなら、配列がすでに整列されていたとしても、未ソート領域から最小値を探すために毎回比較を行う必要があるからです。Bubble Sortの最適化版のように、交換が一度も発生しなければ早期終了するという構造ではありません。そのため、入力データの状態に関係なく、比較回数は大きく変わりません。
一方で、Selection Sortは交換回数が比較的少ないという特徴があります。各ステップで最小値を探し、必要であれば現在位置と一度だけ交換します。そのため、隣接要素を何度も交換するBubble Sortと比べると、交換処理の回数は少なくなりやすいです。ただし、比較回数が多いため、大規模データを扱う場合には効率的とはいえません。Selection Sortは、計算量や交換回数の違いを理解するための学習用アルゴリズムとして捉えるのが適切です。
4.1 時間計算量
Selection Sortは二重ループを使うため、時間計算量はO(n^2)になります。外側のループでは現在位置を順番に進め、内側のループでは残りの未ソート領域を走査します。最初のステップではほぼ全体を比較し、次のステップでは一つ少ない範囲を比較します。このように比較範囲は少しずつ短くなりますが、全体としては要素数に対して二次的に比較回数が増えていきます。
この性質により、Selection Sortは要素数が少ない場合には問題なく動作しますが、要素数が多くなると処理が重くなります。たとえば、学習用に数個から数十個の配列を扱う程度であれば問題ありませんが、数千件や数万件のデータをSelection Sortで並び替えるのは現実的ではありません。実務では標準のArray.prototype.sort()を使い、Selection Sortは時間計算量を学ぶための教材として扱うとよいでしょう。
4.2 空間計算量
Selection Sortは、元の配列を直接変更する実装であれば、追加の大きなメモリを必要としません。最小値のインデックスを保存する変数や、交換時に使う一時的な変数程度で済むため、空間計算量はO(1)と考えられます。これは、配列のサイズが大きくなっても、追加で使うメモリ量がほとんど増えないという意味です。アルゴリズムの比較では、時間計算量だけでなく空間計算量も重要な観点になります。
ただし、この記事のように元の配列を守るために[...numbers]でコピーを作る場合は、配列サイズ分の追加メモリを使います。この場合、実装全体としてはコピー分のメモリが必要になります。学習用コードでは元データを変更しない安全な書き方を優先することが多いですが、アルゴリズムそのものとしてはインプレースに実装できる点もSelection Sortの特徴です。実務では、可読性、安全性、メモリ使用量のバランスを考えて実装方法を選ぶことが大切です。
4.3 安定性について
Selection Sortは、基本的な実装では安定ソートではない場合があります。安定ソートとは、同じ値を持つ要素の元の順序を維持するソートのことです。たとえば、同じスコアを持つユーザーが複数いる場合、ソート後も元の登録順を保ちたいことがあります。このようなケースでは、安定性が重要になります。Selection Sortでは、最小値を見つけて現在位置と交換する処理によって、同じ値の順序が入れ替わる可能性があります。
オブジェクト配列を扱う実務では、ソートの安定性が表示結果に影響することがあります。たとえば、同じ価格の商品を元の登録順のまま表示したい場合や、同じ日付の記事を元の並び順で残したい場合です。JavaScriptの標準sort()は現代の仕様では安定ソートとして扱われますが、自作アルゴリズムを使う場合は安定性を自分で意識する必要があります。Selection Sortを学ぶときは、単に並び替え結果だけでなく、同じ値を持つ要素の順序がどうなるかにも注目すると理解が深まります。
5. Selection Sortを学ぶポイント
Selection Sortを学ぶときは、最小値を探す処理と交換処理を分けて理解することが重要です。外側のループは現在位置を決める役割を持ち、内側のループは未ソート領域から最小値を探す役割を持ちます。そして、最小値のインデックスが分かったら現在位置と交換します。この役割分担を意識すると、コードの構造が分かりやすくなります。単にコードを暗記するのではなく、各変数が何を表しているのかを確認しながら学びましょう。
また、Selection SortはBubble SortやInsertion Sortと比較しながら学ぶと理解が深まります。同じO(n^2)の基本ソートでも、Bubble Sortは隣接要素を何度も交換し、Insertion Sortはソート済み領域に要素を挿入します。一方、Selection Sortは未ソート領域から最小値を選んで現在位置に置きます。この違いを理解することで、アルゴリズムごとの特徴や得意不得意が見えてきます。
5.1 小さな配列で手順を確認する
Selection Sortを初めて学ぶときは、[4, 2, 3, 1]のような小さな配列で処理を追うのがおすすめです。要素数が少ない配列であれば、どの値が最小値として選ばれ、どの位置と交換されるのかを簡単に確認できます。最初のステップでは配列全体から最小値を探し、次のステップでは先頭を除いた範囲から最小値を探します。この流れを手で追うことで、Selection Sortの基本動作が理解しやすくなります。
小さな配列を使うと、ソート済み領域と未ソート領域の変化も見えやすくなります。1回目の処理が終わると先頭が確定し、2回目の処理が終わると2番目までが確定します。このように、左側から順番に確定していく様子を確認することが大切です。JavaScriptコードを実行する前に、紙やメモで配列の変化を書いてみると、コードとアルゴリズムの動きがつながりやすくなります。
5.2 minIndexの役割を理解する
Selection Sortでは、minIndexの役割を理解することが非常に重要です。minIndexは、現在の未ソート領域の中で最も小さい値がある位置を記録する変数です。内側のループでより小さい値が見つかるたびに、minIndexをその位置に更新します。ループが終わった時点で、minIndexには未ソート領域の最小値の位置が入っています。このインデックスを使って、現在位置と最小値の位置を交換します。
初心者がつまずきやすいのは、最小値そのものではなく、最小値のインデックスを保存する理由です。値だけを保存しても、配列内のどの要素と交換すればよいのかが分かりにくくなります。インデックスを保存しておけば、交換対象の位置を正確に指定できます。JavaScriptの配列操作では、値とインデックスの両方を意識する場面が多いため、Selection Sortを通じてインデックス管理に慣れておくと、他の処理にも応用しやすくなります。
5.3 実務では標準sortを使う
Selection Sortは学習用として非常に有用ですが、実務で大量データを並び替える目的には向いていません。時間計算量がO(n^2)であるため、要素数が増えると処理が重くなりやすいからです。実務では、JavaScript標準のArray.prototype.sort()を使うのが一般的です。標準メソッドはエンジン側で最適化されており、通常の一覧表示やデータ処理では十分に高性能です。
ただし、Selection Sortを学ぶことは標準sort()を正しく使うためにも役立ちます。比較対象をどう決めるか、値をどのように並べ替えるか、昇順と降順で条件がどう変わるかを理解できるためです。実務では標準メソッドを使い、学習ではSelection Sortを自分で実装してアルゴリズムの考え方を身につけるという使い分けが現実的です。Selection Sortを理解しておくと、他のソートアルゴリズムを学ぶときの土台にもなります。
おわりに
Selection Sortは、未ソート領域から最小値を選び、現在位置と交換するシンプルなソートアルゴリズムです。JavaScriptで実装しやすく、最小値探索、インデックス管理、交換処理、二重ループの理解に役立ちます。左側からソート済み領域が広がっていく構造が分かりやすいため、初心者が配列操作やアルゴリズムの基本を学ぶうえで適しています。
一方で、Selection Sortの時間計算量はO(n^2)であり、大規模データには向いていません。実務では標準のArray.prototype.sort()を使うことが多く、Selection Sortは主に学習目的で扱われます。Selection Sortを理解すると、Bubble SortやInsertion Sortとの違いが分かりやすくなり、ソートアルゴリズム全体への理解も深まります。次にInsertion SortやMerge Sortを学ぶことで、より幅広い並び替え手法を理解できるようになるでしょう。
