[理工] sorted list
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
推
12/18 12:07, , 1F
12/18 12:07, 1F
→
12/18 12:07, , 2F
12/18 12:07, 2F
→
12/18 12:07, , 3F
12/18 12:07, 3F
→
12/18 12:12, , 4F
12/18 12:12, 4F
→
12/18 12:13, , 5F
12/18 12:13, 5F
→
12/18 13:01, , 6F
12/18 13:01, 6F
→
12/18 13:15, , 7F
12/18 13:15, 7F
→
12/18 13:25, , 8F
12/18 13:25, 8F
→
12/18 14:03, , 9F
12/18 14:03, 9F
推
12/19 17:48, , 10F
12/19 17:48, 10F