PTT數位生活區 / C_and_CPP (C/C++)

[問題] quicksort原地迴圈的寫法

看板C_and_CPP (C/C++)作者 (Tidus)時間7年前 (2018/12/21 19:44), 編輯推噓3(3推 0噓 53→)
留言56則, 4人參與, 7年前最新討論串1/1
開發平台(Platform): (Ex: Win10, Linux, ...) win10 編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出) gcc 4.8.1 額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) no 問題(Question)： 想要寫一個quicksort不用遞迴且不用另外開矩陣的寫法， 不過選pivot後第一次都拆成兩個小陣列結束後就不知道開如何做了。 餵入的資料(Input)： 預期的正確結果(Expected Output)： 錯誤結果(Wrong Output)： 程式碼(Code)：(請善用置底文網頁, 記得排版，禁止使用圖檔) void swap(int *a, int *b){ int temp = *a; *a = *b; *b = temp; } void quicksort(int a[], int array_length){ int left_bound = 0, right_bound = array_length-1; int right = right_bound, left = left_bound, pivot = (left+right)/2; int i, j; int new_left_bound, new_right_bound; int pivot_zero, pivot_one; while(left < right) { if(a[right] > a[pivot]) { if (a[left] < a[pivot]) { right--; left++; } else right--; } else { if (a[left] < a[pivot]) left++; else { swap(&a[left],&a[right]); right--; left++; } } if(left == right) { new_left_bound = right+1; new_right_bound = left; left = left_bound; right = new_right_bound; pivot = (left+right)/2; } if(left == pivot)break; printf("%d %d %d\n",right,left,pivot); } } 補充說明(Supplement)： 感覺這種divide and conquer用迴圈做比較難， 網路上找的版本也幾乎都是遞迴的版本， 除了遞迴比較好寫外有其他原因嗎?? -- ！！！！！！！！！！！！！簽名檔破740000點擊率啦！！！！！！！！！！！！！！！ Fw: [問卦] 電影：決勝21點的機率問題 https://goo.gl/2BpbB7 #1MfN3FgZ (joke)
→
07/22 16:41,
chx64的1/2悖論真的很經典呢
07/22 16:41
！！！！！！！！！！！！！！簽名檔破740000點擊率啦！！！！！！！！！！！！！！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.9.136.149 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1545392640.A.7A6.html
→
12/21 20:00, 7年前 , 1F
你要怎麼知道有那些區間是 partition 完但還沒 merge 的?
12/21 20:00, 1F
→
12/21 22:41, 7年前 , 2F
原地排列應該沒有合併的問題吧
12/21 22:41, 2F
→
12/21 23:39, 7年前 , 3F
簡單說 DaC 還會需要整合結果的步驟, 所以我問 partition
12/21 23:39, 3F
→
12/21 23:40, 7年前 , 4F
完, 你去處理完更小的區間以後, 要怎麼回來處理其他區間?
12/21 23:40, 4F
→
12/21 23:43, 7年前 , 5F
即使是 in-place quicksort 也有回去處理上個 partition
12/21 23:43, 5F
→
12/21 23:44, 7年前 , 6F
剩下來另一半區間的步驟, 也會有整合結果的步驟 (雖然可以
12/21 23:44, 6F
→
12/21 23:45, 7年前 , 7F
不做事), 但就跟遞迴呼叫類似, 你要用同份程式碼執行在不
12/21 23:45, 7F
→
12/21 23:46, 7年前 , 8F
同情境 (context) 下, 先要有辦法把情境資訊給儲存起來
12/21 23:46, 8F
→
12/21 23:49, 7年前 , 9F
這個問題也是我現在正在想的，目前的code只能一直往
12/21 23:49, 9F
→
12/21 23:49, 7年前 , 10F
左或是一直往右。中間的小陣列初步的想法是設定兩個
12/21 23:49, 10F
→
12/21 23:49, 7年前 , 11F
新的變數存新的邊界去跑，不過這邊就是要想想怎麼寫
12/21 23:49, 11F
→
12/21 23:49, 7年前 , 12F
，寫出來還要在看看是不是O(nlogn)
12/21 23:49, 12F
→
12/21 23:50, 7年前 , 13F
不過merge sort就比較好找到迭代版本的code
12/21 23:50, 13F
→
12/22 00:04, 7年前 , 14F
用 LIFO stack 去存當前區間、pivot、階段就可以了
12/22 00:04, 14F
→
12/22 04:25, 7年前 , 15F
這邊有兩種實作可以對照看 https://bit.ly/2T2HEOH
12/22 04:25, 15F
→
12/22 09:41, 7年前 , 16F
如果可以接受多 O(log n) 的空間應該還好寫就是了
12/22 09:41, 16F
→
12/22 09:42, 7年前 , 17F
另外其實 divide 有很好懂的寫法, 不一定要左右交換
12/22 09:42, 17F
→
12/22 10:40, 7年前 , 18F
感謝兩位的分享，不過我看網路上資料in place的快排
12/22 10:40, 18F
→
12/22 10:40, 7年前 , 19F
才是最快的，其他都比合併排序慢
12/22 10:40, 19F
推
12/22 16:19, 7年前 , 20F
stack存還沒排過的區間
12/22 16:19, 20F
推
12/22 23:55, 7年前 , 21F
還會是 in-place 呀, Quicksort 本來就要 O(log n) 的
12/22 23:55, 21F
→
12/22 23:55, 7年前 , 22F
堆疊空間
12/22 23:55, 22F
→
12/23 00:00, 7年前 , 23F
實際用的 sorting algorithm 記得都是好幾種的混合
12/23 00:00, 23F
→
12/23 22:50, 7年前 , 24F
但我看網路上的資料是說不需要另外開陣列給他，而且i
12/23 22:50, 24F
→
12/23 22:50, 7年前 , 25F
n place應該也只是陣列內的元素交換而已
12/23 22:50, 25F
→
12/23 23:10, 7年前 , 26F
那有個問題: 你定義區域變數要不要算進空間複雜度? 你進行
12/23 23:10, 26F
→
12/23 23:10, 7年前 , 27F
遞迴呼叫算不算配置記憶體?
12/23 23:10, 27F
→
12/23 23:52, 7年前 , 28F
我找到的資料。 https://reurl.cc/moQQ7
12/23 23:52, 28F
→
12/23 23:54, 7年前 , 29F
我目前的想法空間複雜度應該只是常數，但我還沒實現
12/23 23:54, 29F
→
12/24 02:32, 7年前 , 30F
再研究一下 in-place algorithm 指的是哪方面的 in-place
12/24 02:32, 30F
→
12/24 02:34, 7年前 , 31F
吧, 如果 quicksort 空間複雜度可以到常數你就可以得獎了
12/24 02:34, 31F
→
12/24 09:17, 7年前 , 32F
那如果只是單純在原陣列中排序為何還需要其他空間
12/24 09:17, 32F
→
12/24 09:25, 7年前 , 33F
喔看來是我誤會in-place的意思了
12/24 09:25, 33F
推
12/24 13:40, 7年前 , 34F
那個 O(log n) 是遞迴的堆疊空間, 在原本的 quicksort
12/24 13:40, 34F
→
12/24 13:41, 7年前 , 35F
就有. 手寫堆疊多多少少可以變迴圈的形式, 而且
12/24 13:41, 35F
→
12/24 13:41, 7年前 , 36F
quicksort 的遞迴方式很簡單, 寫出來應該也不會太難懂
12/24 13:41, 36F
→
12/24 13:42, 7年前 , 37F
當然我個人是喜歡寫成遞迴的形式. 遞迴跟歸納法一樣,
12/24 13:42, 37F
→
12/24 13:42, 7年前 , 38F
遞迴呼叫想成 "由歸納假設", 就可以把陣列排好了
12/24 13:42, 38F
→
12/24 14:22, 7年前 , 39F
我看過msort的遞迴確實比迭代簡單，qsort遞迴也蠻好
12/24 14:22, 39F
→
12/24 14:22, 7年前 , 40F
寫的，但是個人是喜歡迭代
12/24 14:22, 40F
→
12/24 15:01, 7年前 , 41F
O(log N) 不是專指遞迴需要的空間, 而是為了 divide &
12/24 15:01, 41F
→
12/24 15:02, 7年前 , 42F
conquer 需要記住的資訊量, 你用 iterative 因為也要記錄
12/24 15:02, 42F
→
12/24 15:03, 7年前 , 43F
相同資訊, 所以免不了這部分的空間複雜度. recursive 只是
12/24 15:03, 43F
→
12/24 15:03, 7年前 , 44F
把資訊存在 call stack 上, 這樣的分別而已
12/24 15:03, 44F
→
12/24 15:14, 7年前 , 45F
把遞迴跟 divide & conquer 劃上等號就錯了, 應該從了解演
12/24 15:14, 45F
→
12/24 15:16, 7年前 , 46F
算法本身著手. divide 我也可以開好多條 thread 去作, 討
12/24 15:16, 46F
→
12/24 15:16, 7年前 , 47F
論實作根本無助於理解這個 O(log N)
12/24 15:16, 47F
→
12/24 15:37, 7年前 , 48F
hint: O(log N) 跟演算法是 top-down 有關
12/24 15:37, 48F
→
12/24 16:26, 7年前 , 49F
你會覺得 iterative merge sort 實作很好理解的原因在於即
12/24 16:26, 49F
→
12/24 16:27, 7年前 , 50F
使用 bottom-up approach 去實作也很容易, 因為邊界都可以
12/24 16:27, 50F
→
12/24 16:27, 7年前 , 51F
在一開始的時候全算出來, 但對於 top-down 的演算法, 想要
12/24 16:27, 51F
→
12/24 16:30, 7年前 , 52F
把 "分出子問題" 這件事跟 "解決問題本身" 成本相仿, 你如
12/24 16:30, 52F
→
12/24 16:31, 7年前 , 53F
實作出完全迴圈版, 會發現成本都在儲存子問題資訊上面,
12/24 16:31, 53F
→
12/24 16:32, 7年前 , 54F
空間複雜度 O(N log N), 為了蒐集資訊需額外付出時間成本
12/24 16:32, 54F
→
12/24 16:32, 7年前 , 55F
O(N log N)
12/24 16:32, 55F
→
12/24 23:19, 7年前 , 56F
你說得對
12/24 23:19, 56F
‣ 更多 j0958322080 的文章
文章代碼(AID): #1S7D80Uc (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 j0958322080 的文章
文章代碼(AID): #1S7D80Uc (C_and_CPP)