ソートアルゴリズムの基礎を深める
みなさんこんにちは！
ワンキャリアのOCC（ONE CAREER CLOUD）チームで開発エンジニアを担当しているJustin（Github：justin3-1）です。
今回はソートアルゴリズムについて、個人的に学んだ内容をまとめたいと思います！
はじめに
アルゴリズムは、プログラマーにとっては欠かせない重要なスキルの1つです。開発業務においてソートアルゴリズムを直接使用する機会は、それほど多くないかもしれません。ただ、ソートアルゴリズムをしっかりと理解しておくことで、ソースコードの読解力UPやプログラミングスキル全体を向上させることができます。そのため、業務で複雑な問題に出会った際に、その問題を解決するための基盤づくりに役立ちます。
自分もWEB系のエンジニアとして、普段実装する時に利用しているprogramming languageの仕組みには、必ずソートアルゴリズムを利用しています！
本記事では、ソートアルゴリズムをテーマに、基本的な3つのソート手法（バブルソート、選択ソート、挿入ソート）を紹介します。各アルゴリズムの特徴をより分かりやすく理解していただけるように基本的な考え方から始め、その次に時間計算量・空間計算量の分析を行い、コード例を交えつつ説明していく予定です。そして最後には、各アルゴリズムの長所と短所をまとめ、より効率的に理解できるように説明していきます。
ソートアルゴリズムの基礎知識
①バブルソート（Bubble Sort）
バブルソートは、各反復処理（イテレーション）において隣接する要素を比較し、大きい要素を徐々に末尾へと“バブルアップ”させることで、配列全体を並び替えるアルゴリズムです。この処理を繰り返すことで、最終的に配列がソートされます。
数学的な観点から見ると、バブルソートの本質は、逆転対（Inversion）を段階的に解消していくことにあります。隣接する要素を比較し交換するたびに、配列内の逆転対の数が減少します。配列内にn個の逆転対が存在する場合、バブルソートでは最低でも n回の交換操作が必要になります。
シンプルな実装
function bubbleSort(arr) {
let len = arr.length;
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // swap
}
}
}
return arr;
}
また、最適化の方針も様々存在します。
早期終了の最適化
swapped フラグを使って要素の交換が発生したかを記録し、交換がない場合はソートが完了していると判断して早期終了することで、無駄なループを回避することができます。
function bubbleSortOptimized(arr) {
let len = arr.length;
for (let i = 0; i < len - 1; i++) {
let swapped = false; // フラグ変数、交換が発生したかを検出
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true; // 交換が発生
}
}
if (!swapped) break; // 交換が発生しなかった場合、配列は既にソート済みのため早期終了
}
return arr;
}
まとめ
時間計算量：O(n²)
空間計算量：O(1)
安定性：安定
②選択ソート（Selection Sort）
選択ソートは、未ソートの部分から最小の要素を選び、ソート済み部分の末尾に配置することを繰り返すことで、配列を整列するアルゴリズムです。この操作を配列全体で実行することで、完全なソートが完成します。
シンプルな実装
function selectionSort(arr) {
let len = arr.length;
for (let i = 0; i < len - 1; i++) {
let minIndex = i; // 現在の位置が最小値だと仮定
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // より小さい要素が見つかった場合、最小値のインデックスを更新
}
}
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // 位置を交換
}
}
return arr;
}
最適化
未ソート部分は毎回全てを遍歴する必要があるため、最適化することができます。これにより、既にソートされている部分を毎回遍歴する必要がなくなります。
最適化のポイント：
isSorted フラグを使用して、現在のラウンドで交換が発生したかどうかをチェックします。交換が発生しなかった場合、配列は既にソート済みであるため、早期に終了できます。
これは、ほぼソートされているか、一部だけソートされた配列に対して特に効果的であり、不必要な反復を避けることができます。
function selectionSortOptimized(arr) {
let len = arr.length;
for (let i = 0; i < len - 1; i++) {
let minIndex = i;
let isSorted = true; // 現在のラウンドで交換が発生したかどうかを示すフラグ
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
isSorted = false; // より小さい要素が見つかった場合、交換が発生したことを示す
}
}
if (isSorted) break; // 交換が発生しなかった場合、残りの部分はすでにソート済みなので、早期終了
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; // 位置を交換
}
}
return arr;
}
まとめ
時間計算量：O(n²)
空間計算量：O(1)
安定性：不安定（同じ値の要素の相対的な順序が維持されない場合がある）
重要な特徴は、交換回数が少ない（最大でもN-1回）ことです。書き込みコストが高い環境に適しています。
③挿入ソート（Insertion Sort）
挿入ソートは、未ソートの要素を1つずつ取り出し、ソート済みの部分のに適切な位置へ挿入することで整列を行うアルゴリズムです。
このソートの最大の強みは、一部が既に整列された配列に対して非常に効率的に動作する点です！
シンプルな実装
function insertionSort(arr) {
let len = arr.length;
// 1つ目の要素はすでにソートされているとみなすので、2つ目の要素から開始
for (let i = 1; i < len; i++) {
let current = arr[i]; // 現在の要素を保存
let j = i - 1; // 現在の要素の前のインデックスを指す
// 現在の要素が前の要素より小さい場合、前の要素を1つ後ろに移動
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j]; // 1つ後ろに移動
j--; // 前の要素に移動
}
// 現在の要素が正しい位置に配置される
arr[j + 1] = current; // 現在の要素を適切な位置に配置
}
return arr;
}
最適化
二分探索のことを知らないエンジニアはいないと思いますが、挿入ソートも二分探索によって最適化することができます。移動操作を減らすために、最適化版の挿入ソートでは、現在の要素が挿入されるべき位置を見つけるために二分探索を使用しています。二分探索を使うことで、適切な挿入位置をより迅速に見つけ、不必要な比較操作を減らすことができます。
function insertionSortOptimized(arr) {
let len = arr.length;
// 1つ目の要素はすでにソートされているとみなすので、2つ目の要素から開始
for (let i = 1; i < len; i++) {
let current = arr[i]; // 現在の要素を保存
let j = i - 1; // 現在の要素の前のインデックスを指す
// 現在の要素が前の要素より小さい場合、前の要素を1つ後ろに移動
// ここでは、移動操作を減らすためにバイナリサーチを使用
let left = 0;
let right = j;
// バイナリサーチを使って挿入位置を見つける
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] < current) {
left = mid + 1;
} else {
right = mid - 1;
}
}
// 挿入位置に要素をシフト
while (j >= left) {
arr[j + 1] = arr[j];
j--;
}
// 正しい位置に現在の要素を挿入
arr[j + 1] = current;
}
return arr;
}
まとめ
挿入ソートの時間計算量は、配列内の逆転対（Inversion）の数 に直接関係します。
逆転対の数に対して、時間計算量は O(n + k)
完全にソート済みの配列：O(n)
完全に逆順の配列：O(n²)
安定性：安定（同じ値の要素の相対的な順序を保持）
プログラミング言語のソースコードの例
最初に述べた通り、私たちが毎日使っているプログラミング言語の仕組みには、実際に多くのソートアルゴリズムが使われています。
しかし、プログラミング言語の実装では、状況が非常に複雑なことが多いため、1つのアルゴリズムだけでは全ての問題を解決することができません。そのため、最適な実装を達成するために、様々なアルゴリズムの長所を組み合わせる必要があります。
その中で登場したソートアルゴリズムの1つとして、今回はTimSortを紹介いたします。
TimSortとは？
TimSortは、2002年にTim Petersによって開発された高効率なハイブリッドソートアルゴリズムです。現在では以下のような多くのシステムでデフォルトのソートアルゴリズムとして採用されています。
・Google ChromeのV8 JavaScriptエンジン
・Python（組み込みのsorted()、リストの.sort()）
このアルゴリズムの最大の特徴は、「いろんなソートアルゴリズム、insertion sort, quick sort, merge sort」の長所を組み合わせることで、部分的にソート済みのデータを効率的に処理できる点にあります。
Google ChromeのV8 JavaScript
Python SDK
最後に
普段の開発では、こういったことを意識することはあまりなく、機能の開発に集中しがちです。 そのため、時々ソースコードを見ても「なんだか
難しそう」と感じることもあるかもしれません。
しかし、多くの複雑な内容の本質は、シンプルな要素が組み合わさったものです。 基礎的な本質をしっかり理解していれば、より複雑な内容に取り組む際も、きっとスムーズに理解できるようになるでしょう。
このような学習を続けていけば、プログラマーとしての思考力も大きく向上していくはずです！
「人の数だけ、キャリアをつくる。」
ワンキャリアではミッション実現のために、事業・プロダクト開発を推進させる仲間を募集しています。弊社のエンジニア組織にご興味を持っていただけた方は、採用情報もチェックいただけると嬉しいです！
▼ワンキャリアのエンジニア組織のことを知りたい方はまずこちら
▼カジュアル面談を希望の方はこちら
▼エンジニア求人票
