作者Rioronja (Rioronja)
看板Grad-ProbAsk
標題[理工] 資結 Inplace
時間Wed Feb 27 13:24:54 2019
到底什麼是inplace
記得當初寫考古的時候也有看到這個字
上網查了資料
卻都沒有清楚定義
有沒有能抽絲剝繭一下inplace的概念
今年好多學校都有考這個
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.254.34.219
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1551245097.A.CF4.html
1F：推 Dora5566: 在原本input空間用交換的方式排序 02/27 13:33
2F：→ Rioronja: Dora大 可是我看有人寫說QuickSort不是in place的 02/27 13:33
3F：推 wilson50101: sorting in place就是只說只靠原來input的資料結構的 02/27 13:34
4F：→ Dora5566: 會考這個的學校都已經考完了 02/27 13:34
5F：→ wilson50101: 空間來做swap而完成排序 02/27 13:34
6F：→ wilson50101: 不需要依靠另外的空間完成 02/27 13:34
7F：→ wilson50101: eg inplace有quicksort heapsort等 02/27 13:34
8F：→ wilson50101: not inplace有mergesort 02/27 13:34
9F：→ Rioronja: 可是他是實作SWAP來排序的啊 02/27 13:34
10F：→ wilson50101: quicksort是inplace 因為他的額外空間是靠遞迴的stac 02/27 13:35
11F：→ wilson50101: k產生的跟排序無關 02/27 13:35
12F：→ Rioronja: 了解！！所以可以定義說如果是用SWAP來SORTING的 02/27 13:36
13F：→ Rioronja: 都是inplace的吧ㄥ 02/27 13:36
14F：推 Dora5566: 不是吧 不是用SWAP就會是inplace 02/27 13:39
15F：→ Dora5566: 是inplace只能用SWAP 02/27 13:39
18F：→ Rioronja: 我考前看維基百科裡面，確實把Quick定義成非inplace 02/27 13:43
19F：→ Rioronja: 對！Dora大跟我看得一樣，所以Quicksort怎麼分類啊！！ 02/27 13:44
20F：推 wilson50101: 補習的時候洪逸老師是講quicksort是inplace 02/27 13:45
21F：→ wilson50101: 可能這部分有爭議吧我覺得 02/27 13:45
22F：→ Rioronja: 看來要去看原文書了 不過我那時候翻原文書怎麼沒看到 02/27 13:47
23F：→ Rioronja: inplace的定義啊 02/27 13:47
24F：推 Dora5566: 這個最好是去查學校的ptt 畢竟改考卷的是教授 02/27 13:51
25F：→ Dora5566: 我本來也以為quicksort是inplace 現在看起來我也不知道 02/27 13:52
26F：→ Dora5566: 惹 02/27 13:52
27F：→ Rioronja: 照百科上的定義，只要要用到遞迴的演算法，因為至少要用 02/27 13:58
28F：→ Rioronja: 一個Stack來追蹤，所以就不是inplace。 02/27 13:58
29F：→ Rioronja: 看很多人則是在意在排序過程中，有沒有使用額外空間 02/27 13:59
30F：推 TWkobe: 這定義蠻無聊的 你用linked list實作還會in place？ 02/27 16:44
31F：推 hodo: 感覺著重的點是有無額外空間？就是空間複雜度 02/27 18:01
33F：→ yp195126: 台大那題基準為最右 看起來應該是True? 02/27 20:57
34F：→ Rioronja: 樓上大大們 我看各個網路上的分類，有的是以上面說的空 02/27 22:31
35F：→ Rioronja: 間複雜度去做判別的，也有是說因為quick一定會用到遞迴 02/27 22:31
36F：→ Rioronja: ，遞迴使用額外的資料結構也就是stack來協助運作，所以 02/27 22:31
37F：→ Rioronja: 非in place。癥結點應該在是在sorting 的中間來看，還是 02/27 22:31
38F：→ Rioronja: 以整個實作面來看。說實在的，討論這個很無聊，又不會因 02/27 22:31
39F：→ Rioronja: 為我們定義他是不是in place實作上會有差異，也沒有in p 02/27 22:31
40F：→ Rioronja: lace額外會附帶什麼性質，純粹是考題考出來一翻兩瞪眼， 02/27 22:31
41F：→ Rioronja: 事前有做準備也會因為個人觀點不同而相左。純粹碎念～ 02/27 22:31
44F：推 ekids1234: 洪毅說 inplace ? 可是筆記我在看的時候寫需遞迴 02/28 02:16
45F：→ ekids1234: 就想說洪毅應該也認為不是 .. ? 02/28 02:17
46F：→ hodo: cute大，給的圖是說插入排序是inplace吧？還說看錯了 02/28 02:42
47F：→ cutearia: 第一張是quick的partition 第二張是in place定義 02/28 06:27
49F：→ cutearia: 補一下 貼16頁的原因 覺得考試照楓葉比較好 02/28 06:36
50F：推 hodo: 是說quicksort有分有無inplace的版本 就看教授認為是哪個了 02/28 07:41
51F：→ hodo: 吧.. 然後額外用logn 太小就可以忽略 說是inplace的樣子? 02/28 07:41
52F：推 xcnx123: 只用到額外O(1)空間的就是inplace，依照這標準去算就可以 03/05 21:18
53F：→ xcnx123: 判斷了 03/05 21:18