ホームページ ウェブフロントエンド jsチュートリアル バブルソート、選択ソート、挿入ソート | JavaScript のデータ構造とアルゴリズム

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

Sep 03, 2024 am 11:43 AM

Bubble Sort, Selection Sort, Insertion Sort | Data Structures & Algorithms in JavaScript

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

バブルソート

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

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

// 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(n2) です。

// 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(n2) です。

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 サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

Video Face Swap

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

フロントエンドのサーマルペーパーレシートのために文字化けしたコード印刷に遭遇した場合はどうすればよいですか? フロントエンドのサーマルペーパーレシートのために文字化けしたコード印刷に遭遇した場合はどうすればよいですか? Apr 04, 2025 pm 02:42 PM

フロントエンドのサーマルペーパーチケット印刷のためのよくある質問とソリューションフロントエンド開発におけるチケット印刷は、一般的な要件です。しかし、多くの開発者が実装しています...

javascriptの分解:それが何をするのか、なぜそれが重要なのか javascriptの分解:それが何をするのか、なぜそれが重要なのか Apr 09, 2025 am 12:07 AM

JavaScriptは現代のWeb開発の基礎であり、その主な機能には、イベント駆動型のプログラミング、動的コンテンツ生成、非同期プログラミングが含まれます。 1)イベント駆動型プログラミングにより、Webページはユーザー操作に応じて動的に変更できます。 2)動的コンテンツ生成により、条件に応じてページコンテンツを調整できます。 3)非同期プログラミングにより、ユーザーインターフェイスがブロックされないようにします。 JavaScriptは、Webインタラクション、シングルページアプリケーション、サーバー側の開発で広く使用されており、ユーザーエクスペリエンスとクロスプラットフォーム開発の柔軟性を大幅に改善しています。

誰がより多くのPythonまたはJavaScriptを支払われますか? 誰がより多くのPythonまたはJavaScriptを支払われますか? Apr 04, 2025 am 12:09 AM

スキルや業界のニーズに応じて、PythonおよびJavaScript開発者には絶対的な給与はありません。 1. Pythonは、データサイエンスと機械学習でさらに支払われる場合があります。 2。JavaScriptは、フロントエンドとフルスタックの開発に大きな需要があり、その給与もかなりです。 3。影響要因には、経験、地理的位置、会社の規模、特定のスキルが含まれます。

Shiseidoの公式Webサイトのように、視差スクロールと要素のアニメーション効果を実現する方法は?
または:
Shiseidoの公式Webサイトのようにスクロールするページを伴うアニメーション効果をどのように実現できますか? Shiseidoの公式Webサイトのように、視差スクロールと要素のアニメーション効果を実現する方法は? または: Shiseidoの公式Webサイトのようにスクロールするページを伴うアニメーション効果をどのように実現できますか? Apr 04, 2025 pm 05:36 PM

この記事の視差スクロールと要素のアニメーション効果の実現に関する議論では、Shiseidoの公式ウェブサイト(https://www.shisido.co.co.jp/sb/wonderland/)と同様の達成方法について説明します。

JavaScriptは学ぶのが難しいですか? JavaScriptは学ぶのが難しいですか? Apr 03, 2025 am 12:20 AM

JavaScriptを学ぶことは難しくありませんが、挑戦的です。 1)変数、データ型、関数などの基本概念を理解します。2)非同期プログラミングをマスターし、イベントループを通じて実装します。 3)DOM操作を使用し、非同期リクエストを処理することを約束します。 4)一般的な間違いを避け、デバッグテクニックを使用します。 5)パフォーマンスを最適化し、ベストプラクティスに従ってください。

JavaScriptの進化:現在の傾向と将来の見通し JavaScriptの進化:現在の傾向と将来の見通し Apr 10, 2025 am 09:33 AM

JavaScriptの最新トレンドには、TypeScriptの台頭、最新のフレームワークとライブラリの人気、WebAssemblyの適用が含まれます。将来の見通しは、より強力なタイプシステム、サーバー側のJavaScriptの開発、人工知能と機械学習の拡大、およびIoTおよびEDGEコンピューティングの可能性をカバーしています。

JavaScriptを使用して、同じIDを持つArray要素を1つのオブジェクトにマージする方法は? JavaScriptを使用して、同じIDを持つArray要素を1つのオブジェクトにマージする方法は? Apr 04, 2025 pm 05:09 PM

同じIDを持つ配列要素をJavaScriptの1つのオブジェクトにマージする方法は?データを処理するとき、私たちはしばしば同じIDを持つ必要性に遭遇します...

Zustand非同期操作:UseStoreが取得した最新の状態を確保する方法は? Zustand非同期操作:UseStoreが取得した最新の状態を確保する方法は? Apr 04, 2025 pm 02:09 PM

Zustand非同期操作のデータの更新問題。 Zustand State Management Libraryを使用する場合、非同期操作を不当にするデータ更新の問題に遭遇することがよくあります。 �...

See all articles