視覚化でわかるソートアルゴリズム

JavaScriptのソートアルゴリズムを視覚的に理解

ソート（並び替え）アルゴリズムは、データ構造とアルゴリズムの基本を理解する第１段階です。ソートアルゴリズムを理解してデータの並び替えを最適化するだけでもデータ処理のパフォーマンス向上に有用です。この知識は、JavaScriptだけでなく、他のプログラミング言語にも応用可能です。

ソート（並び替え）の動きを視覚化

次のサンプルでは、各ソートアルゴリズムを視覚化しています。
各ソートボタンを押して動作を確かめる前にリロードボタンでバーを並べ替えてください。

See the Pen visual-sort-func2 by k2zo_o (@k2zo_o) on CodePen.

アニメーションを分かりやすくするためにゆっくり動かしています。

バブルソート（Bubble Sort）

バブルソートは、隣接する要素を比較し、順序が逆であれば交換するというシンプルなアルゴリズムです。

・配列の左から右へスキャンしていきます。
・隣接する要素を比較し、逆の順序であれば交換します。
・このプロセスを配列がソートされるまで繰り返します。

コード例

function bubbleSort(arr) {
  let swapped;
  do {
    swapped = false;
    for (let i = 0; i < arr.length - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        swapped = true;
      }
    }
  } while (swapped);
  return arr;
}

選択ソート（Selection Sort）

選択ソートは、配列の中で最小（または最大）の要素を探し、先頭の要素と交換するアルゴリズムです。

・配列の左端から始め、未ソート部分の最小の要素を見つけます。
・その要素を未ソート部分の先頭と交換します。
・未ソート部分がなくなるまで繰り返します。

コード例

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        /* */
         minIndex = j;
      }
    }
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
  return arr;
}

挿入ソート（Insertion Sort）

挿入ソートは、配列を順次スキャンし、各要素を適切な位置に挿入していくアルゴリズムです。

・配列の2番目の要素から始めます。
・現在の要素を、ソート済み部分の適切な位置に挿入します。
・これを最後の要素まで繰り返します。

コード例

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let current = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
  return arr;
}

クイックソート（Quick Sort　）

クイックソートは、ピボットを選び、ピボットより小さい要素は左に、大きい要素は右に配置する分割統治アルゴリズムです。

・ピボット要素を選びます（通常は配列の中央など）。
・ピボットより小さい要素を左に、大きい要素を右に移動します。
・左右の部分配列に対して再帰的に同じ操作を行います。

コード例（一部省略）

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  let pivot = arr[0];
  let left = [];
  let right = [];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }
  return [...quickSort(left), pivot, ...quickSort(right)];
}

マージソート（Merge Sort）

マージソートも分割統治アルゴリズムで、配列を2つの部分に分割し、それぞれをソートしてから統合します。

・配列を2つの等しい部分に分割します。
・それぞれの部分をソートします（通常は再帰的に）。
・ソートされた部分を統合します。

コード例（一部省略）

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  let mid = Math.floor(arr.length / 2);
  let left = mergeSort(arr.slice(0, mid));
  let right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  let result = [];
  while (left.length && right.length) {
    if (left[0] < right[0]) result.push(left.shift());
    else result.push(right.shift());
  }
  return [...result, ...left, ...right];
}