[理工] 資結 Inplace

看板Grad-ProbAsk作者 (Rioronja)時間6年前 (2019/02/27 13:24), 編輯推噓13(13040)
留言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: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: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:34, 6年前 , 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: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
文章代碼(AID): #1STXyfpq (Grad-ProbAsk)