使用 Javascript 進行演算法之旅 - 冒泡排序

什麼是冒泡排序？

冒泡排序是計算機科學中最簡單的排序演算法之一。它以每次迭代時較小的元素“冒泡”到列表頂部的方式命名，是教授排序演算法基礎知識的絕佳工具。雖然對於大型資料集來說不是最有效的，但它的簡單性使其成為理解排序演算法如何運作的一個很好的起點。

冒泡排序的工作原理

冒泡排序的工作原理是重複遍歷列表，比較相鄰元素，如果順序錯誤則交換它們。重複這個過程，直到不再需要交換為止，表示清單已排序。

這是一步一步的細分：

1. 從數組中的第一個元素開始。
2. 將其與下一個元素進行比較。
3. 如果第一個元素大於第二個元素，則交換它們。
4. 移動到下一個元素並重複步驟 2-3，直到到達陣列末端。
5. 如果進行了任何交換，請從頭開始重複此過程。
6. 如果完整傳遞中沒有進行交換，則陣列已排序。

讓我們可視化這個過程：

R錄製的 gif 來自 https://visualgo.net/en/sorting

在 JavaScript 中實作冒泡排序

讓我們研究一下 JavaScript 中冒泡排序的三種實現，每種實現的最佳化等級都在增加。

基本實作 (v1)

這個基本實作使用巢狀循環來比較和交換相鄰元素。外循環確保我們對數組進行了足夠的遍歷，而內循環則執行比較和交換。

優化實作 (v2)

此版本引入了交換標誌來檢查一次傳遞中是否進行了任何交換。如果沒有發生交換，則清單已經排序，我們可以提前跳出循環。

最優化的實作 (v3)

最後的最佳化在每次傳遞中將內部循環的範圍減少了 i。這是因為每次傳遞後，最大的未排序元素「冒泡」到陣列末端的正確位置。

時間與空間複雜度分析

冒泡排序的性能特點如下：

• 時間複雜度：

  • 最佳情況：O(n) - 當陣列已經排序時
  • 平均情況：O(n^2)
  • 最壞情況：O(n^2) - 當陣列逆序時

• 空間複雜度：O(1) - 冒泡排序是一種就地排序演算法，只需要恆定量的額外記憶體。

與快速排序（平均 O(n log n)）或合併排序（O(n log n)）等更高級的演算法相比，冒泡排序的二次時間複雜度使其對於大型資料集效率低下。

冒泡排序的優點和缺點

優點：

• 易於理解與實作
• 就地排序（O(1) 空間）
• 穩定的排序演算法
• 可以偵測已經排序的清單

缺點：

• 對於大型資料集效率低（O(n^2)）
• 在接近排序的數據上表現不佳
• 過多的交換操作

何時使用冒泡排序

• 教育目的：它的簡單性使其非常適合教授基本演算法概念。
• 小資料集：對於非常小的數組，與複雜演算法相比，效能差異可能可以忽略不計。
• 近排序資料：透過最佳化版本，在近排序清單上可以相當有效率。
• 有限的記憶體環境：它的就地性質在記憶體極度受限的場景中非常有利。

雞尾酒排序：改進的變體

雞尾酒排序，也稱為雞尾酒搖排序或雙向冒泡排序，是冒泡排序的改進版本。它雙向遍歷列表，有助於更有效地將元素移動到正確的位置。

How Cocktail Sort Works

1. Start with the first element and move towards the end, swapping adjacent elements if they're in the wrong order.
2. When you reach the end, start from the second-to-last element and move towards the beginning, again swapping elements as needed.
3. Repeat this process, narrowing the range of elements to check with each pass, until no swaps are needed.

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

Cocktail Sort implementation in Javascript

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.

Practical Applications and Use Cases

While Bubble Sort isn't typically used in production environments for large-scale applications, it can still find use in certain scenarios:

1. Educational tools: It's often used to introduce sorting algorithms and algorithm analysis in computer science education.
2. Embedded systems: In systems with very limited memory, its in-place sorting can be advantageous.
3. Small datasets: For sorting small lists (e.g., less than 50 elements), its simplicity might outweigh the performance benefits of more complex algorithms.
4. Nearly sorted data: If data is known to be almost sorted, an optimized Bubble Sort can be reasonably efficient.
5. Sorting stability requirement: When a stable sort is needed and simplicity is preferred over efficiency, Bubble Sort can be a straightforward choice.

Conclusion

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:

• It's simple to understand and implement.
• It has a time complexity of O(n^2), making it inefficient for large datasets.
• It's an in-place and stable sorting algorithm.
• Optimizations can improve its performance, especially for nearly sorted data.
• It's primarily used for educational purposes and in scenarios with very small datasets or limited memory.

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中文網其他相關文章！