推 fjf1980:謝謝，或許此quicksort的pivot不是用第1或最後一個，那就 02/27 19:47
→ fjf1980:不是worst case, 就可能會是average case,我這樣解讀 02/27 19:48
※ 引述《fjf1980 (聽說 侯佩岑是豬頭)》之銘言：
: for internal sorting algorithm:selection sort, insertion sort, bubble sort,
: and quick sort.
: which method runs faster for a file in reverse order?
: 答案是Quick sort,
: 我的疑問：
: reverse order對Quick sort是worst case, O(N平方)
: selection sort的O(N平方),且selection sort交換固定是n-1次
: 我本來答案寫selction sort, 不懂為何正確答案要選Quick sort,
: 還請高手指教！！ 感謝！
Quicksort 的實作其實有很多種，
有些版本固定會拿第一個元素當作 pivot，
也有些版本選擇中間的元素，
甚至也有隨機選 pivot，和選九個元素的中位數作 pivot 的版本。
在以上所提版本中，
只有選擇第一個(或是最後一個)作 pivot 的版本，
reverse order 才會是 worst case。
假設題目真是這個意思，那毫無疑問，
Quicksort 的 average case 時間複雜度確實就是較低。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.78.231