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