在最佳情況下Bubblesorting 25個元素的陣列

以下應用/理論問題出現在我的算法類中，我得到了來自我的教授和TA的相互矛盾的答案。在最佳情況下Bubblesorting 25個元素的陣列

在（a）最差的情況下需要多少次比較來對數組進行冒泡？（b）最好的情況？

我知道，標準冒泡算法是

for i = 0 to n - 2 for j = n - 1 to i + 1 if A[j - 1] > A[j] swap(A[j - 1], A[j])

其實我用Google搜索這個問題和問題的答案其實是分別300和24。但我對這裏的「比較」一詞感到困惑。我們認爲什麼是比較？我們是否認爲它只是if檢查自己，或者它執行的代碼塊是否正確？在最壞的情況下，交換和if語句將執行總計n(n-1)/2次。然而，在最佳情況下，if聲明將像以前一樣檢查有效性n(n-1)/2次，但由於數組在最佳情況下排序，因此不會發生交換。這意味着最差情況和最好情況下的比較次數是相同的，不是嗎？

我的教授說「比較」的意思是「比較這兩個要素」，但沒有更多解釋。我的電訊局長認爲這可能基於for循環的執行次數。

雖然它讓我變得更加困惑：我們如何從算法的這個定義中提取出最好情況下的bubblesort爲O(n)？顯然，在最好的情況下不會發生交換，但內循環將在外循環中爲每個值i運行，因此算法會遍歷數組n(n-1)/2次。究竟什麼是n-1次這裏，給我們O(n)？

我找到的原始問題的答案使用優化的bubblesort算法，該算法僅使用1 for循環，如果沒有交換髮生，則退出。這是一個更好的算法來使用這個問題嗎？即，

bubblesort_optimized(A) assume we are not done sorting while we are not done sorting assume we're done sorting traverse the list element by element from i = 1 to n - 1. if A[i-1] > A[i], swap if a swap occurs, we are not done sorting

在這種特殊情況下，這是令人難以置信明顯在這一切的來源。但是講座和我們的書中的算法從來沒有提到這一點。

感謝您的閱讀！

來源

2016-06-18 Decaf-Math

我們認爲什麼是比較？我們是否認爲它只是if檢查本身，或者它執行的代碼塊是否正確？

只是if檢查。但是，在最糟糕的情況下，交換次數完全相同，這是正確的。

從這個算法的定義中，我們如何從最好的情況下提取bubblesort是O（n）？

你是絕對正確的，你使用的實現是而不是 O（n）在最好的情況下。你需要做一個小的優化，以使其停止時，有在內部循環中沒有互換：

bool done = false 
while (!done) 
    done = true 
    for j = n - 1 to i + 1 
     if A[j - 1] > A[j] 
       swap(A[j - 1], A[j]) 
       done = false

這樣外環會因爲沒有在內部循環中完成掉期儘快停止。在最好的情況下，內部循環的第一次迭代也將是最後一次迭代，產生預期的O（n）次比較。

來源

2016-06-18 00:47:19 dasblinkenlight

我們認爲什麼是比較？

if聲明是比較。這是測試任何內容的代碼片段中的唯一代碼。

這意味着最差情況和最好情況下的比較次數是相同的，不是嗎？

有了這段代碼，是的。

從這個算法的定義中，我們如何從最好的情況下提取bubblesort爲O(n)？

這不是，根據以前的答案。

跳過你的最後一個問題（因爲它回答了其餘的）：

答案原來的問題，我發現使用只使用1 for循環優化的冒泡排序算法，如果沒有交換髮生退出。這是一個更好的算法來使用這個問題嗎？

這可能是更復雜的，取決於它的寫法，但在優化比較次數方面，它會更好。

來源

2016-06-18 00:44:28 MSN

對於這個確切的僞代碼，所做比較的次數總是相同的，因爲代碼每次都進行相同的比較。請注意，這段代碼並沒有做什麼冒泡排序通常會做的事情，一旦通過發生不發生交換的情況下就會突然退出循環，所以它實際上不會在時間O（n）中運行最好的情況。此代碼總是需要時間Θ（n ）。事實上，我真的不會因爲這個原因而調用該代碼冒泡排序。

如果更新代碼以便在未對底層數組進行更改時跳出外循環，則會開始獲得更有趣的模式和行爲。這就是你得到O（n）最佳情況下的運行時間，在最佳情況下進行的24次比較，等等。

來源

2016-06-18 00:45:46 templatetypedef

for i = 0 to n - 2 
    for j = n - 1 to i + 1 
     if A[j - 1] > A[j] 
      swap(A[j - 1], A[j])

正如你所建議的，這裏進行的比較是第三行。我認爲其中有意義的部分是我們將A的兩個元素相互比較。 A [j-1]和A [j]。我們在這裏做的具體比較比對比要大。（X1> X2？）我們正在研究兩個元素並確定它們之間的關係。

我已經實際上Google了這個問題，問題的答案實際上分別是300和24。

這對於n的具體值而言並不是所有n的情況都是如此。 n是數組中元素的數量，當我們談論時間複雜性時，它們通常是參考我們正在查看的集合的大小。

來源

2016-06-18 00:49:43

在最佳情況下Bubblesorting 25個元素的陣列

回答

相關問題