配列整列処理の基本アルゴリズム

データ集合の整列は基礎的な処理であり、アルゴリズムの理解に不可欠です。ここでは実用的な実装例を示します。

バブルソート

隣接要素を比較し、昇順に並べ替える基本アルゴリズムです。最適化として、各パスで確定した最大値を除外する範囲を狭めます。

function arrangeByBubble(data) {
  const total = data.length;
  for (let outer = 0; outer < total - 1; outer++) {
    let swapped = false;
    for (let inner = total - 1; inner > outer; inner--) {
      if (data[inner] < data[inner - 1]) {
        [data[inner], data[inner - 1]] = [data[inner - 1], data[inner]];
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return data;
}

選択ソート

未整列領域から最小値を選択し、整列領域の末尾に追加する方式です。交換回数が少ないのが特徴です。

function selectAndArrange(elements) {
  const count = elements.length;
  for (let position = 0; position < count - 1; position++) {
    let smallestIndex = position;
    for (let candidate = position + 1; candidate < count; candidate++) {
      if (elements[candidate] < elements[smallestIndex]) {
        smallestIndex = candidate;
      }
    }
    if (smallestIndex !== position) {
      [elements[position], elements[smallestIndex]] = 
      [elements[smallestIndex], elements[position]];
    }
  }
  return elements;
}

挿入ソート

整列済み領域を拡張しながら要素を適切な位置に挿入します。部分的に整列されたデータに効果的です。

function insertSorted(collection) {
  for (let currentIndex = 1; currentIndex < collection.length; currentIndex++) {
    const targetValue = collection[currentIndex];
    let comparisonIndex = currentIndex - 1;
    
    while (comparisonIndex >= 0 && collection[comparisonIndex] > targetValue) {
      collection[comparisonIndex + 1] = collection[comparisonIndex];
      comparisonIndex--;
    }
    collection[comparisonIndex + 1] = targetValue;
  }
  return collection;
}

マージソート

分割統治法に基づく安定ソートです。配列を再帰的に分割し、整列後にマージします。

function mergeSortedArrays(input) {
  if (input.length <= 1) return input;
  
  const splitPoint = Math.floor(input.length / 2);
  const leftPart = mergeSortedArrays(input.slice(0, splitPoint));
  const rightPart = mergeSortedArrays(input.slice(splitPoint));
  
  return combineHalves(leftPart, rightPart);
}

function combineHalves(first, second) {
  const result = [];
  let i = 0, j = 0;
  
  while (i < first.length && j < second.length) {
    result.push(first[i] <= second[j] ? first[i++] : second[j++]);
  }
  
  return result.concat(first.slice(i)).concat(second.slice(j));
}

クイックソート

ピボット要素を基準に分割し、再帰的に整列する効率的なアルゴリズムです。

function quickArrange(items, start = 0, end = items.length - 1) {
  if (start >= end) return items;
  
  const pivotIndex = partitionArray(items, start, end);
  quickArrange(items, start, pivotIndex - 1);
  quickArrange(items, pivotIndex + 1, end);
  
  return items;
}

function partitionArray(array, low, high) {
  const pivotValue = array[Math.floor((low + high) / 2)];
  
  while (low <= high) {
    while (array[low] < pivotValue) low++;
    while (array[high] > pivotValue) high--;
    
    if (low <= high) {
      [array[low], array[high]] = [array[high], array[low]];
      low++;
      high--;
    }
  }
  return low;
}