ホームページ > 記事 > ウェブフロントエンド > Javascript を使用したアルゴリズムの旅 - バブルソート
バブル ソートは、コンピューター サイエンスにおける最も単純なソート アルゴリズムの 1 つです。反復のたびに小さな要素がリストの先頭に「バブル」する様子にちなんで名付けられたこのツールは、並べ替えアルゴリズムの基本を教えるための優れたツールです。大規模なデータセットにとっては最も効率的ではありませんが、そのシンプルさは、並べ替えアルゴリズムがどのように機能するかを理解するための優れた出発点になります。
バブル ソートは、リストを繰り返しステップ実行し、隣接する要素を比較し、順序が間違っている場合は入れ替えることによって機能します。このプロセスは、スワップが必要なくなるまで繰り返され、リストがソートされたことが示されます。
段階的に詳しく説明します:
このプロセスを視覚化してみましょう:
https://visualgo.net/en/sorting から録画した GIF
それぞれ最適化レベルを上げながら、JavaScript でのバブル ソートの 3 つの実装を調べてみましょう。
function bubbleSort(list) { // Outer loop: iterate through the entire list for (let i = 0; i < list.length - 1; i++) { // Inner loop: compare adjacent elements for (let j = 0; j < list.length - 1; j++) { // If the current element is greater than the next one if (list[j] > list[j + 1]) { // Swap the elements using destructuring assignment [list[j], list[j + 1]] = [list[j + 1], list[j]]; } } } // Return the sorted list return list; }
この基本的な実装では、ネストされたループを使用して、隣接する要素を比較および交換します。外側のループは配列内で十分なパスを実行することを保証し、内側のループは比較と交換を実行します。
function bubbleSort(list) { // Outer loop: iterate through the entire list for (let i = 0; i < list.length - 1; i++) { // Flag to check if any swaps occurred in this pass let swapped = false; // Inner loop: compare adjacent elements for (let j = 0; j < list.length - 1; j++) { // If the current element is greater than the next one if (list[j] > list[j + 1]) { // Swap the elements using destructuring assignment [list[j], list[j + 1]] = [list[j + 1], list[j]]; // Set the swapped flag to true swapped = true; } } // If no swaps occurred in this pass, the list is sorted if (!swapped) { break; // Exit the outer loop early } } // Return the sorted list return list; }
このバージョンでは、パス内でスワップが行われたかどうかを確認するためのスワップ済みフラグが導入されています。スワップが発生しない場合、リストはすでにソートされているため、ループを早期に抜け出すことができます。
function bubbleSort(list) { // Outer loop: iterate through the entire list for (let i = 0; i < list.length - 1; i++) { // Flag to check if any swaps occurred in this pass let swapped = false; // Inner loop: compare adjacent elements // Note: We reduce the upper bound by i in each pass for (let j = 0; j < list.length - 1 - i; j++) { // If the current element is greater than the next one if (list[j] > list[j + 1]) { // Swap the elements using destructuring assignment [list[j], list[j + 1]] = [list[j + 1], list[j]]; // Set the swapped flag to true swapped = true; } } // If no swaps occurred in this pass, the list is sorted if (!swapped) { break; // Exit the outer loop early } } // Return the sorted list return list; }
この最後の最適化により、各パスで内側のループの範囲が i ずつ減少します。これは、各パスの後、ソートされていない最大の要素が配列の末尾の正しい位置に「バブルアップ」するためです。
バブルソートのパフォーマンス特性は次のとおりです:
時間計算量:
空間複雑さ: O(1) - バブル ソートはインプレース ソート アルゴリズムであり、一定量の追加メモリのみを必要とします。
クイック ソート (平均 O(n log n)) やマージ ソート (O(n log n)) などのより高度なアルゴリズムと比較して、バブル ソートの二次時間計算量により、大規模なデータセットの場合は非効率的になります。
利点:
欠点:
カクテル ソートは、カクテル シェイク ソートまたは双方向バブル ソートとも呼ばれ、バブル ソートの改良版です。これはリストを両方向に走査し、要素をより効率的に正しい位置に移動するのに役立ちます。
Cocktail Sort is particularly useful in cases where the array has elements that are initially large at the beginning and small at the end, as it can reduce the total number of passes needed compared to traditional Bubble Sort.
Here's a visualization of Cocktail Sort:
Visual from Wikipedia: https://en.wikipedia.org/wiki/Cocktail_shaker_sort
function cocktailSort(list) { let swapped; // The do...while loop ensures the sorting continues until no swaps are needed do { // Reset the swapped flag at the beginning of each complete iteration swapped = false; // First pass: left to right (like standard bubble sort) for (let i = 0; i < list.length - 1; i++) { // If the current element is greater than the next, swap them if (list[i] > list[i + 1]) { [list[i], list[i + 1]] = [list[i + 1], list[i]]; // Mark that a swap occurred swapped = true; } } // If no swaps occurred in the first pass, the array is sorted if (!swapped) { break; // Exit the do...while loop early } // Reset the swapped flag for the second pass swapped = false; // Second pass: right to left (this is what makes it "cocktail" sort) for (let i = list.length - 2; i >= 0; i--) { // If the current element is greater than the next, swap them if (list[i] > list[i + 1]) { [list[i], list[i + 1]] = [list[i + 1], list[i]]; // Mark that a swap occurred swapped = true; } } // The loop will continue if any swaps occurred in either pass } while (swapped); // Return the sorted list return list; }
This implementation alternates between forward and backward passes through the list, potentially reducing the number of iterations needed to sort the array.
While Bubble Sort isn't typically used in production environments for large-scale applications, it can still find use in certain scenarios:
Bubble Sort, despite its inefficiencies with large datasets, offers valuable insights into the world of sorting algorithms and algorithm analysis. Its straightforward approach makes it an excellent teaching tool for beginners in computer science.
Key takeaways are:
While you're unlikely to use Bubble Sort in production code for large-scale applications, the principles behind it are fundamental to many algorithms. The process of optimizing Bubble Sort teaches valuable lessons about algorithm improvement, serving as a stepping stone to more advanced computational problem-solving.
When it comes to algorithms, there's rarely a one-size-fits-all solution. The best algorithm for a given task depends on the specific requirements, constraints, and characteristics of your data. Bubble Sort, with all its limitations, still has its place in this diverse algorithmic ecosystem.
以上がJavascript を使用したアルゴリズムの旅 - バブルソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。