ソートアルゴリズムの初歩的な探求

バブルソート#

バブルソートは、シンプルなソートアルゴリズムです。ソートする配列を繰り返し訪れ、2 つの要素を比較し、順序が間違っている場合は交換します。配列の訪問作業は、交換が不要になるまで繰り返され、つまり配列がソートされるまで行われます。このアルゴリズムの名前は、より小さい要素がゆっくりと配列の先頭に「浮かび上がる」ためです。

バブルソートアルゴリズムの動作は次のとおりです：

隣接する要素を比較します。最初の要素が 2 番目の要素よりも大きい場合、それらを交換します。
各隣接する要素のペアに対して同じ作業を行います。最後の要素は最大の数になります。
最後の要素を除いて、すべての要素に対して上記の手順を繰り返します。
要素の数が少なくなるごとに、上記の手順を繰り返し、比較する必要のある数字のペアがなくなるまで続けます。

バブルソートの平均時間計算量は O (n^2) であり、最良の場合、つまり一度のソートで完了する場合の計算量は O (n) であり、最悪の場合の計算量は O (n^2) です。

クラシックなバブルソートアルゴリズム#

クラシックなバブルソートアルゴリズム：2 重のループを使用してソートを実現し、外側のループは現在のソートのラウンドを表し、内側のループは現在のラウンドのソートの回数を表します。2 つの要素を比較し、位置を交換してソートを完了します。

function bubbleSort(nums) {
  const len = nums.length
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (nums[j] > nums[j + 1]) {
        ;[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]] // 位置を交換
      }
    }
  }
  return nums
}

改良されたバブルソートアルゴリズム#

改良されたバブルソートアルゴリズム：pos というフラグ変数を設定し、各ソートラウンドの最後の交換位置を記録します。pos の位置以降のレコードはすでに交換されているため、次のソートラウンドでは pos の位置までスキャンするだけで十分です。

function bubbleSort(nums) {
  const len = nums.length
  let i = len - 1
  while (i > 0) {
    let pos = 0
    for (let j = 0; j < i; j++) {
      if (nums[j] > nums[j + 1]) {
        pos = j // 交換時の位置を記録
        ;[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]] // 位置を交換
      }
    }
    i = pos
  }
  return nums
}

アルティメットバブルソートアルゴリズム#

アルティメットバブルソートアルゴリズム：伝統的なバブルソートでは、各ラウンドのソート操作で最大値または最小値のいずれか 1 つしか見つけることができません。アルティメットバブルソートでは、各ソートラウンドで正方向と逆方向の 2 回のバブル操作を行い、2 つの最終値（最大値と最小値）を 1 回のソートで得ることができます。これにより、ソートのラウンド数がほぼ半分に減少します。

function bubbleSort(nums) {
  let low = 0
  let high = nums.length - 1
  let i
  while (low < high) {
    // 正方向のソート、最大値を見つける
    for (i = low; i < high; ++i) {
      if (nums[i] > nums[i + 1]) {
        ;[nums[i], nums[i + 1]] = [nums[i + 1], nums[i]] // 位置を交換
      }
    }
    --high // 1つ前に移動

    // 逆方向のソート、最小値を見つける
    for (i = high; i > low; --i) {
      if (nums[i] < nums[i - 1]) {
        ;[nums[i], nums[i - 1]] = [nums[i - 1], nums[i]] // 位置を交換
      }
    }
    ++low // 1つ後に移動
  }
  return nums
}

選択ソート#

選択ソートは、シンプルで直感的なソートアルゴリズムです。未ソートのシーケンスから最小（または最大）の要素を見つけて、ソート済みのシーケンスの末尾に配置します。残りの未ソートの要素から最小（または最大）の要素を見つけて配置し、これを繰り返します。これにより、すべての要素がソートされるまで続けられます。

選択ソートアルゴリズムの動作は次のとおりです：

初期状態では、未ソートの領域は R [1..n] であり、ソート済みの領域は空です。
i 番目のソートが開始されると、現在のソート済みの領域と未ソートの領域はそれぞれ R [1..i-1] と R [i..n] です。次に、未ソートの領域から最小値を選択し、それを未ソートの領域の最初の値と交換します。これにより、ソート済みの領域が 1 つ増え、未ソートの領域が 1 つ減ります。
n-1 回のソートが終了すると、配列全体がソート済みの領域になり、ソートが完了します。

選択ソートの主な利点は、データの移動に関連しています。要素が正しい最終位置にある場合、移動されません。選択ソートは、1 対の要素を交換するたびに少なくとも 1 つの要素が最終位置に移動されるため、n 個の要素からなるリストをソートするために最大で n-1 回の交換が行われます。要素の移動に頼らない完全に交換によって要素を移動するソート方法の中で、選択ソートは非常に優れています。

選択ソートの平均時間計算量は O (n^2) です。

クラシックな選択ソートアルゴリズム#

クラシックな選択ソートアルゴリズム：配列をソート済み領域と未ソート領域の 2 つの部分に分割し、各ラウンドで未ソート領域から最小値を選択してソート済み領域に組み込み、ソート済み領域を 1 つ増やし、未ソート領域を 1 つ減らします。n - 1 回のソート後、すべての要素がソート済み領域になり、ソートが完了します。

function selectionSort(nums) {
  const len = nums.length
  let min = 0
  for (let i = 0; i < len - 1; i++) {
    min = i
    for (let j = i + 1; j < len; j++) {
      if (nums[min] > nums[j]) {
        min = j // 最小値のインデックスを保存
      }
    }
    ;[nums[i], nums[min]] = [nums[min], nums[i]] // 位置を交換
  }
  return nums
}

挿入ソート#

挿入ソートは、シンプルなソートアルゴリズムです。ソート済みのデータ列を構築し、未ソートのデータをソート済みのデータ列内で後方から前方にスキャンし、適切な位置に挿入します。挿入ソートは、実装上、インプレースソートを使用するため、後方にスキャンする際にソート済みの要素を逐次的に後方に移動する必要があります。

挿入ソートアルゴリズムの動作は次のとおりです：

最初の要素から開始し、その要素は既にソートされていると見なされます。
次の要素を取り出し、ソート済みの要素列内で後方にスキャンし、新しい要素が適切な位置に挿入されるまで、ソート済みの要素を逐次的に後方に移動します。
スキャンが終了すると、新しい要素はソート済みの要素列内の適切な位置に挿入されます。
上記の手順 2〜3 を繰り返し、ソートが完了します。

挿入ソートの平均時間計算量は O (n^2) であり、最良の場合、つまりソート済みの配列をソートする場合の計算量は O (n) であり、最悪の場合の計算量は O (n^2) です。

クラシックな挿入ソートアルゴリズム#

クラシックな挿入ソートアルゴリズム：配列をソート済み領域と未ソート領域の 2 つの部分に分割し、各ラウンドで未ソート領域から要素を取り出し、ソート済み領域内で後方にスキャンし、適切な位置に挿入します。これにより、ソート済み領域が 1 つ増え、未ソート領域が 1 つ減ります。

function insertionSort(nums) {
  const len = nums.length
  for (let i = 1; i < len; i++) {
    let k = nums[i]
    let j = i - 1
    while (j >= 0 && nums[j].num > k.num) {
      nums[j + 1] = num[j]
      j--
    }
    nums[j + 1] = k
  }
  return nums
}

二分挿入ソートアルゴリズム#

二分挿入ソートアルゴリズム：挿入位置の検索に二分探索の方法を使用し、挿入する値が比較する必要のある左端を見つけます。データの長さが大きい場合、ソートの各ラウンドで挿入位置を検索する回数を効果的に減らすことができます。

function insertionSort(nums) {
  const len = nums.length
  for (let i = 1; i < len; i++) {
    let k = nums[i]
    let left = 0
    let right = i - 1
    while (left <= right) {
      let middle = ~~((left + right) / 2)
      if (k < nums[middle]) {
        right = middle - 1
      } else {
        left = middle + 1
      }
    }
    for (let j = i - 1; j >= left; j--) {
      nums[j + 1] = nums[j]
    }
    nums[left] = k
  }
  return nums
}

マージソート#

マージソートは、マージ操作に基づいて効率的なソートアルゴリズムです。マージ操作は、2 つの既にソートされたシーケンスを 1 つのシーケンスにマージする操作を指します。マージソートの時間計算量は O (nlogn) です。このアルゴリズムは、分割統治法の非常に典型的な応用であり、各レベルの分割再帰は同時に実行できます。

マージソートアルゴリズムの動作は次のとおりです：

長さ n のシーケンスを 2 つの部分シーケンスに分割し、それぞれをソートします。ソートされた各シーケンスは、2 つの要素または 1 つの要素を含むシーケンスとなります。
ソートされた 2 つのシーケンスをマージし、1 つのソートされたシーケンスを作成します。これにより、各レベルの分割再帰が同時に実行されます。
上記の手順 2 を繰り返し、シーケンスが完全にソートされるまで続けます。
マージソートの平均時間計算量は O (nlogn) です。

クラシックなマージソートアルゴリズム#

クラシックなマージソートアルゴリズム：配列を 2 つのサブシーケンスに分割し、サブシーケンスの長さが 1 でない場合は再帰的にサブシーケンスをさらに分割します。2 つのサブシーケンスを比較してソートし、互いに組み合わせてソートされたシーケンスを作成します。最終的に、完全にソートされたシーケンスが得られます。

function mergeSort(nums) {
  const len = nums.length
  if (len <= 1) return nums
  let middle = ~~(len / 2)
  let left = nums.slice(0, middle)
  let right = nums.slice(middle)
  return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
  const result = []
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      result.push(left.shift())
    } else {
      result.push(right.shift())
    }
  }
  return result.concat(left, right)
}
}