PTT數位生活區 / Python

[問題] Quick Sort陷入無窮遞迴

看板Python作者時間7年前 (2018/04/15 15:25), 7年前編輯推噓8(8推 0噓 12→)
留言20則, 8人參與, 7年前最新討論串1/1
版上各位前輩好， 小弟是入門者，最近教授出題要寫qsort， 概念是對list選取一pivot， 比他小的都放左邊，大的放右邊， 如此重複，直到完整排序。 我的寫法如下圖： http://i.imgur.com/PyV2XzW.jpg
最後return的時候不知道該怎麼讓遞迴關係在達到排序完畢時停止，不知道要怎麼設條件， 應該說有想到用len=1做停止條件， 但不知道該放在哪裡， 資質駑鈍，還請各位多多指教包涵。 上網查別人寫好的都需要定義很多函式再互相呼叫，還是那才是唯一解呢? 2018/4/16 21:00 感謝各位的回覆 終於開竅了 http://i.imgur.com/sKZFl2f.jpg
----- Sent from my ASUSSSSSSSSSSSSS . 作者: gvi86113 (歐派king) 看板: Python 標題: [問題] Quick Sort陷入無窮遞迴 時間: Sun Apr 15 15:25:33 2018 版上各位前輩好， 小弟是入門者，最近教授出題要寫qsort， 概念是對list選取一pivot， 比他小的都放左邊，大的放右邊， 如此重複，直到完整排序。 我的寫法如下圖： http://i.imgur.com/PyV2XzW.jpg
最後return的時候不知道該怎麼讓遞迴關係在達到排序完畢時停止，不知道要怎麼設條件， 應該說有想到用len=1做停止條件， 但不知道該放在哪裡， 資質駑鈍，還請各位多多指教包涵。 上網查別人寫好的都需要定義很多函式再互相呼叫，還是那才是唯一解呢? ----- Sent from my ASUSSSSSSSSSSSSS . -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.204.97.162 ※ 文章網址: https://www.ptt.cc/bbs/Python/M.1523777136.A.97B.html ※ 編輯: gvi86113 (180.204.97.162), 04/15/2018 15:28:52 ※ 編輯: gvi86113 (180.204.97.162), 04/15/2018 15:46:41 ※ 編輯: gvi86113 (180.204.97.162), 04/15/2018 15:48:05
推
04/15 16:09, 7年前 , 1F
list長度為 1 的時候終止遞迴
04/15 16:09, 1F
我有想到用len(less_lst) = 1做條件，但沒想到應該要放在哪裡 ※ 編輯: gvi86113 (180.204.97.162), 04/15/2018 16:28:04
→
04/15 16:29, 7年前 , 2F
想想看長度1代表什麼
04/15 16:29, 2F
我知道長度=1時，代表已經分割到結果了，可是如果要把條件設進去的話，我反而不知道怎麼再次叫出遞迴了，資質駑鈍還請多包涵 QQ
推
04/15 16:38, 7年前 , 3F
放在第一行,直接 return 長度 1 的list
04/15 16:38, 3F
設條件之後反而不太清楚遞迴該放在哪裡了，目前寫這樣連自己都覺得不合理 http://i.imgur.com/9oCMBkr.jpg
※ 編輯: gvi86113 (180.204.97.162), 04/15/2018 16:52:52 ※ 編輯: gvi86113 (180.204.97.162), 04/15/2018 16:53:55 ※ 編輯: gvi86113 (180.204.97.162), 04/15/2018 17:00:02
→
04/15 20:03, 7年前 , 4F
分割到結果? 你再想想看吧
04/15 20:03, 4F
→
04/15 20:18, 7年前 , 5F
base case: len==1 => return list;
04/15 20:18, 5F
→
04/15 20:19, 7年前 , 6F
take pivot=list[len//2];
04/15 20:19, 6F
→
04/15 20:21, 7年前 , 7F
return quicksort(list_l)+pivot+quicksort(list_u)
04/15 20:21, 7F
→
04/15 20:22, 7年前 , 8F
list_l = list smaller than pivot; list_u, similarly
04/15 20:22, 8F
→
04/15 20:46, 7年前 , 9F
Soory for quick typo: base case: len<=1
04/15 20:46, 9F
→
04/15 20:47, 7年前 , 10F
Apology for typo: "Sorry"... =_=
04/15 20:47, 10F
推
04/15 21:41, 7年前 , 11F
第一次看到qsort是這樣寫
04/15 21:41, 11F
我看到的範例都用好幾個函式互相呼叫 只有我這樣寫嗎qq?
推
04/15 22:25, 7年前 , 12F
你的問題不是qsort,是你根本不會recurion......
04/15 22:25, 12F
因為當下不知道條件怎麼放進去所以就先這樣待補 ><
→
04/15 22:26, 7年前 , 13F
recursion要有明確的終止條件,不然就是無限執行....
04/15 22:26, 13F
推
04/15 23:12, 7年前 , 14F
你的new_list = ... 那一行的右邊 qsort 應該是打錯了
04/15 23:12, 14F
→
04/15 23:13, 7年前 , 15F
然後這一行就進入遞迴了 後面的if根本不會被執行到
04/15 23:13, 15F
推
04/15 23:45, 7年前 , 16F
若 len(L) == 1, qsort(L) 應該 return 什麼 ?
04/15 23:45, 16F
推
04/15 23:58, 7年前 , 17F
你這樣能想的清楚每一層會回傳什麼東西嗎...？
04/15 23:58, 17F
→
04/16 00:22, 7年前 , 18F
https://ideone.com/NWnjCu 我其實也沒寫過 試個
04/16 00:22, 18F
推
04/16 09:30, 7年前 , 19F
資料結構用python上蠻稀奇的
04/16 09:30, 19F
→
04/16 10:42, 7年前 , 20F
MIT EECS也是用Python上Alg & Data Structures
04/16 10:42, 20F
感謝各位回覆 我已經找到解決方法了 晚點補上程式碼 ※ 編輯: gvi86113 (49.215.208.192), 04/16/2018 11:35:31 ※ 編輯: gvi86113 (49.215.208.192), 04/16/2018 11:36:41 ※ 編輯: gvi86113 (49.215.208.192), 04/16/2018 11:37:19 ※ 編輯: gvi86113 (49.215.208.192), 04/16/2018 12:52:56 ※ 編輯: gvi86113 (49.215.208.192), 04/16/2018 12:55:33
‣ 更多 gvi86113 的文章
文章代碼(AID): #1Qqlvmbx (Python)
Python 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 gvi86113 的文章
文章代碼(AID): #1Qqlvmbx (Python)