[理工] sorted list

[cksh8008 (ck)]

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)
→ A4P8T6X9:個沒排的，問要多快才能把後面排進去，直覺好像是inserti
→ A4P8T6X9:on不過貌似不好。
→ kiki86151:第一題我會寫LSD吧 因為可以作為hash sorting用chain
→ kiki86151:至於第二題 是在問可以突破nlogn限制達到O(n)?
→ cksh8008:第二題有查到答案，i是insertion ii是merge sort
→ cksh8008:第二題不是N個排好的，後面要接f(N)個排好的元素嗎
→ kiki86151:應該吧手機排板出問題既然知道題目再問怎我就不解答了
→ cksh8008:真是太感謝前輩了~
推 JaunRiquelme:merge sort