[理工] 資結 Inplace

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