到底什麼是inplace
記得當初寫考古的時候也有看到這個字
上網查了資料
卻都沒有清楚定義
有沒有能抽絲剝繭一下inplace的概念
今年好多學校都有考這個

只用到額外O(1)空間的就是inplace，依照這標準去算就可以判斷了

在原本input空間用交換的方式排序

Dora大 可是我看有人寫說QuickSort不是in place的

sorting in place就是只說只靠原來input的資料結構的

會考這個的學校都已經考完了

可是他是實作SWAP來排序的啊

quicksort是inplace 因為他的額外空間是靠遞迴的stack產生的跟排序無關

了解！！所以可以定義說如果是用SWAP來SORTING的都是inplace的吧ㄥ

不是吧 不是用SWAP就會是inplace是inplace只能用SWAPhttp://i.imgur.com/DmjD1RT.jpg

https://reurl.cc/RzMl9我考前看維基百科裡面，確實把Quick定義成非inplace對！Dora大跟我看得一樣，所以Quicksort怎麼分類啊！！

補習的時候洪逸老師是講quicksort是inplace可能這部分有爭議吧我覺得

看來要去看原文書了 不過我那時候翻原文書怎麼沒看到inplace的定義啊

這個最好是去查學校的ptt 畢竟改考卷的是教授我本來也以為quicksort是inplace 現在看起來我也不知道惹

照百科上的定義，只要要用到遞迴的演算法，因為至少要用一個Stack來追蹤，所以就不是inplace。看很多人則是在意在排序過程中，有沒有使用額外空間

這定義蠻無聊的 你用linked list實作還會in place？

感覺著重的點是有無額外空間？就是空間複雜度

https://i.imgur.com/WXbh5hM.jpg台大那題基準為最右 看起來應該是True?

樓上大大們 我看各個網路上的分類，有的是以上面說的空間複雜度去做判別的，也有是說因為quick一定會用到遞迴，遞迴使用額外的資料結構也就是stack來協助運作，所以非in place。癥結點應該在是在sorting 的中間來看，還是以整個實作面來看。說實在的，討論這個很無聊，又不會因為我們定義他是不是in place實作上會有差異，也沒有in place額外會附帶什麼性質，純粹是考題考出來一翻兩瞪眼，事前有做準備也會因為個人觀點不同而相左。純粹碎念～

洪毅說 inplace ? 可是筆記我在看的時候寫需遞迴就想說洪毅應該也認為不是 .. ?

cute大，給的圖是說插入排序是inplace吧？還說看錯了

第一張是quick的partition 第二張是in place定義https://i.imgur.com/lBYbkNH.png補一下 貼16頁的原因 覺得考試照楓葉比較好

是說quicksort有分有無inplace的版本 就看教授認為是哪個了吧.. 然後額外用logn 太小就可以忽略 說是inplace的樣子?