若資料由小到大排序,則下列有關排序演算法之敘述,何者是錯誤?

題目

若資料由小到大排序,則下列有關排序演算法之敘述,何者是錯誤?

1. (1) 若資料為依序輸入, Insertion Sort 會產生Worst Case
2. (2) 若資料為反序輸入,Quick Sort 會產生Worst Case
3. (3) 若資料為依序輸入,Quick Sort 會產生Worst Case
4. (4) 若資料為反序輸入,Insertion Sort 會產生Worst Case

官方答案

(1) 若資料為依序輸入, Insertion Sort 會產生Worst Case

解析

Insertion Sort 在資料已由小到大排序時，每筆資料只需與前一筆比較一次即可停止，時間複雜度為 O(n)，屬於最佳情況；反而是資料完全反序時，每筆都要往前搬移到底，才是 O(n²) 的最差情況。Quick Sort 若固定取第一個或最後一個元素為基準，資料已排序或完全反序時，分割都會極不平均，退化為 O(n²)。因此「依序輸入會使 Insertion Sort 產生最差情況」的敘述錯誤。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF