版上各位前輩好，
小弟是入門者，最近教授出題要寫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://webptt.com/m.aspx?n=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
1F：推 hadoop: list長度為 1 的時候終止遞迴 04/15 16:09
我有想到用len(less_lst) = 1做條件，但沒想到應該要放在哪裡
※ 編輯: gvi86113 (180.204.97.162), 04/15/2018 16:28:04
2F：→ djshen: 想想看長度1代表什麼 04/15 16:29
我知道長度=1時，代表已經分割到結果了，可是如果要把條件設進去的話，我反而不知道怎麼再次叫出遞迴了，資質駑鈍還請多包涵 QQ
3F：推 hadoop: 放在第一行,直接 return 長度 1 的list 04/15 16:38
設條件之後反而不太清楚遞迴該放在哪裡了，目前寫這樣連自己都覺得不合理
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
4F：→ djshen: 分割到結果? 你再想想看吧 04/15 20:03
5F：→ bowin: base case: len==1 => return list; 04/15 20:18
6F：→ bowin: take pivot=list[len//2]; 04/15 20:19
7F：→ bowin: return quicksort(list_l)+pivot+quicksort(list_u) 04/15 20:21
8F：→ bowin: list_l = list smaller than pivot; list_u, similarly 04/15 20:22
9F：→ bowin: Soory for quick typo: base case: len<=1 04/15 20:46
10F：→ bowin: Apology for typo: "Sorry"... =_= 04/15 20:47
11F：推 TitanEric: 第一次看到qsort是這樣寫 04/15 21:41
我看到的範例都用好幾個函式互相呼叫 只有我這樣寫嗎qq?
12F：推 vfgce: 你的問題不是qsort,是你根本不會recurion...... 04/15 22:25
因為當下不知道條件怎麼放進去所以就先這樣待補 ><
13F：→ vfgce: recursion要有明確的終止條件,不然就是無限執行.... 04/15 22:26
14F：推 mantour: 你的new_list = ... 那一行的右邊 qsort 應該是打錯了 04/15 23:12
15F：→ mantour: 然後這一行就進入遞迴了 後面的if根本不會被執行到 04/15 23:13
16F：推 mantour: 若 len(L) == 1, qsort(L) 應該 return 什麼 ? 04/15 23:45
17F：推 Kazimir: 你這樣能想的清楚每一層會回傳什麼東西嗎...？ 04/15 23:58
19F：推 hihi0123: 資料結構用python上蠻稀奇的 04/16 09:30
20F：→ bowin: MIT EECS也是用Python上Alg & Data Structures 04/16 10:42
感謝各位回覆 我已經找到解決方法了 晚點補上程式碼
※ 編輯: 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