p7.md

Problem

Analyze best-case, average-case, and worst-case performance of the following pseudocode which describes a sorting algorithm. Append your analyzing process or reasons.

i = 2
while i <= size
    if i == 1 or array[i] >= array[i - 1]
        i += 1
    else
        swap array[i], array[i - 1]
        i -= 1

Solution

Best Case

• Answer: O(n) (假設題目中的size為n)
• Explanation:
  • 當array[1…size]中的元素為已排序時(由小排到大)，此sort演算法中的迴圈將執行(size - 1)次，也就是做(size - 1)次比較 (i = 2 ~ size) ，而else的部分不會執行。故Best Case為 O(n) (假設題目中的size為n)

Worst Case

• Answer: O(n²) (假設題目中的size為n)
• Explanation:
  • 當array[1…size]中的元素為由大排到小時，此sort演算法會將較小的元素依序移至array的前端，較大的元素依序移至array的後端。此時，第k個元素所需的比較次數為(2k - 1)次，故size為n的array[1…size]總共所需的比較次數為 3 + 5 +7 + … + (2n–1) = (𝑛²-1)次，故Worst Case為 O(n²)
  • 假設一序列為 10 9 8 7 6 5 4 3 2 1，若使用此sort演算法，則會依序將較小的元素移至陣列最前端(也就是 此序列的第一個位置將會依序為 9 8 7 6… 3 2 1) ，而根據此演算法當發生swap時，會一併執行i-- ，以上面的序列為例 i 的變化為(2 -> 1 -> 2) -> (3 -> 2 -> 1 -> 2 -> 3)->……(10 -> …1… -> 10)
  • 每一個 i 的值都代表著經過一次比較，因此第k個元素所需的比較次數為(2k - 1)次

Average Case

• Answer: O(n²) (假設題目中的size為n)
• Explanation:
  • 第k個元素所需的所有可能比較次數為1、3、5、7…(2k - 1) ，而每種可能的發生機率皆相同，故第k個元素所需的比較次數的期望值為次，設array的size為n，則總比較次數為，故Average Case為O(n²) 。