バブルソート、選択ソート、挿入ソート | JavaScript のデータ構造とアルゴリズム

並べ替えアルゴリズムは多くの計算タスクのバックボーンであり、効率的なアクセスと処理のためにデータを整理する上で重要な役割を果たします。アルゴリズムの世界を探索し始めたばかりの初心者であっても、知識を新たにしたいと考えている熟練の開発者であっても、これらの基本的な並べ替えテクニックを理解することは不可欠です。この投稿では、より基本的なソート アルゴリズムのいくつか、バブル ソート、選択ソート、挿入ソートについて説明します。

バブルソート

バブルソートは、単純な比較ベースのソートアルゴリズムです。リストを繰り返しステップ実行し、隣接する要素を比較し、順序が間違っている場合は入れ替えます。このプロセスは、スワップが必要なくなるまで続き、リストがソートされたことが示されます。バブル ソートは理解と実装が簡単ですが、大規模なデータセットでは非効率的であるため、主に教育目的や小規模なデータ セットに適しています。

バブルソートの時間計算量は O(n²) です。

// a random array of 20 numbers
const inputArray = [34, 100, 23, 45, 67, 89, 12, 56, 78, 90, 23, 45, 67, 89, 12, 56, 78, 90, 23, 45]

function bubbleSort (input) {
  const n = input.length
  const sortedArray = [...input]

  // loop n times
  for (let i = 0; i < n; i++) {
    // loop through all n-1 pairs
    for (let j = 0; j < n-1; j++) {
      // if a > b, swap; else do nothing
      if (sortedArray[j] > sortedArray[j+1]) {
        const temp = sortedArray[j]
        sortedArray[j] = sortedArray[j+1]
        sortedArray[j+1] = temp
      }
    }
  }

  return sortedArray
}

console.log("Input:", inputArray)
console.log("Ouput:", bubbleSort(inputArray))

選択範囲の並べ替え

選択ソートは、単純な比較ベースのソート アルゴリズムです。これは、リストを並べ替えられた領域と並べ替えられていない領域に分割することで機能します。未ソート領域から最小 (または最大) 要素を繰り返し選択し、それを最初の未ソート要素と交換し、ソート済み領域を徐々に拡大します。選択並べ替えは、大規模なデータセットに対して最も効率的ではありませんが、理解しやすく、スワップの数を最小限に抑えるという利点があります。

選択ソートの時間計算量は O(n²) です。

// a random array of 20 numbers
const inputArray = [34, 100, 23, 45, 67, 89, 12, 56, 78, 90, 23, 45, 67, 89, 12, 56, 78, 90, 23, 45]

function selectionSort (input) {
  const n = input.length
  const sortedArray = [...input]

  // loop n times
  for (let i = 0; i < n; i++) {
    // start from i'th position
    let lowestNumberIndex = i
    for (let j = i; j < n-1; j++) {
      // identify lowest number
      if (sortedArray[j] < sortedArray[lowestNumberIndex]) {
        lowestNumberIndex = j
      }
    }

    // swap the lowest number with that in i'th position
    const temp = sortedArray[i]
    sortedArray[i] = sortedArray[lowestNumberIndex]
    sortedArray[lowestNumberIndex] = temp
  }

  return sortedArray
}

console.log("Input:", inputArray)
console.log("Ouput:", selectionSort(inputArray))

挿入ソート

挿入ソートは、一度に 1 要素ずつ最終的にソートされたリストを構築する、直感的な比較ベースのソート アルゴリズムです。これは、リストの未ソート部分から要素を取得し、それらをソート済み部分内の正しい位置に挿入することによって機能します。挿入ソートは、小さなデータセットまたはほぼソートされたデータに対して効率的であり、より複雑なアルゴリズムのより単純な代替手段として実際のアプリケーションでよく使用されます。

挿入ソートの時間計算量は O(n²) です。

function insertionSort (input) {
  const n = input.length
  const sortedArray = [...input]

  // loop n times, starting at index 1
  for (let i = 1; i < n; i++) {
    // start at index 1
    const comparedNumber = sortedArray[i]
    let tempIndex = i

    // compare with previous numbers (right to left)
    for (let j = i-1; j >= 0; j--) {
      // if number in current index is larger than compared number, swap
      if (sortedArray[j] > comparedNumber) {
        sortedArray[tempIndex] = sortedArray[j]
        sortedArray[j] = comparedNumber
        tempIndex = j
      } else {
        // OPTIONAL: else exit
        break
      }
    }
  }

  return sortedArray
}

console.log("Input:", inputArray)
console.log("Ouput:", insertionSort(inputArray))

まとめ

バブル ソート、選択ソート、挿入ソートなどの基本的な並べ替えアルゴリズムは、大規模なデータセットに対しては最も効率的ではないかもしれませんが、アルゴリズムの設計を理解するための優れた基盤となります。この投稿が役に立ったと思われた場合は、ぜひご意見をお聞かせください。以下にコメントを入力して、洞察を共有したり、ご質問があればお問い合わせください。できる限りお答えいたします。

コーディングを楽しんでください!

以上がバブルソート、選択ソート、挿入ソート | JavaScript のデータ構造とアルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。