為什麼這篇Sorted 意思鄉民發文收入到精華區：因為在Sorted 意思這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者cksh8008 (ck)看板Grad-ProbAsk標題[理工] sorted list時間W...
1.Explain the sorting algorithm that is most suitable to be used with single
linked list? You need to explain why your sorting algorithm could be better
then others.
這題我想寫bubble sort
因為bubble sort每回可像array一樣，一開始就讓第一個元素和第二個元素依序往後比
而其他sort演算法，需先移動到第i項才可開始做排序
例如quick sort，光是由後往前找比pivot還小的值每回就需花O(N)^2
而bubble sort執行完成 worst case 為O(N)^2
best case可達O(N)
2.Suppose you are given a sorted list of N elements followed by f(N) randomly
ordered elements. How would you best sort the entire list if
i. f(N) = O(1)
ii. f(N) = O(logN)
iii. f(N) = O(根號N)
iv. f(N) = How large can f(N) be for the entire list still to be sortable in
O(N) time?
其實我不太懂這題再問什麼
希望前輩能指點一下
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.20.242.232
推 A4P8T6X9:第二題題目的意思應該是有N個已經排好的東西後面接f(N) 12/18 12:07
→ A4P8T6X9:個沒排的，問要多快才能把後面排進去，直覺好像是inserti 12/18 12:07
→ A4P8T6X9:on不過貌似不好。 12/18 12:07
→ kiki86151:第一題我會寫LSD吧 因為可以作為hash sorting用chain 12/18 12:12
→ kiki86151:至於第二題 是在問可以突破nlogn限制達到O(n)? 12/18 12:13
→ cksh8008:第二題有查到答案，i是insertion ii是merge sort 12/18 13:01
→ cksh8008:第二題不是N個排好的，後面要接f(N)個排好的元素嗎 12/18 13:15
→ kiki86151:應該吧手機排板出問題既然知道題目再問怎我就不解答了 12/18 13:25
→ cksh8008:真是太感謝前輩了~ 12/18 14:03
推 JaunRiquelme:merge sort 12/19 17:48