开发平台(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

chx64的1/2悖论真的很经典呢

你要怎么知道有那些区间是 partition 完但还没 merge 的?

原地排列应该没有合并的问题吧

简单说 DaC 还会需要整合结果的步骤, 所以我问 partition完, 你去处理完更小的区间以后, 要怎么回来处理其他区间?即使是 in-place quicksort 也有回去处理上个 partition剩下来另一半区间的步骤, 也会有整合结果的步骤 (虽然可以不做事), 但就跟递回呼叫类似, 你要用同份程式码执行在不同情境 (context) 下, 先要有办法把情境资讯给储存起来

这个问题也是我现在正在想的，目前的code只能一直往左或是一直往右。中间的小阵列初步的想法是设定两个新的变量存新的边界去跑，不过这边就是要想想怎么写，写出来还要在看看是不是O(nlogn)不过merge sort就比较好找到迭代版本的code

用 LIFO stack 去存当前区间、pivot、阶段就可以了这边有两种实作可以对照看 https://bit.ly/2T2HEOH

如果可以接受多 O(log n) 的空间应该还好写就是了另外其实 divide 有很好懂的写法, 不一定要左右交换

感谢两位的分享，不过我看网络上资料in place的快排才是最快的，其他都比合并排序慢

chx64的1/2悖论真的很经典呢

你要怎么知道有那些区间是 partition 完但还没 merge 的?

原地排列应该没有合并的问题吧

简单说 DaC 还会需要整合结果的步骤, 所以我问 partition完, 你去处理完更小的区间以后, 要怎么回来处理其他区间?即使是 in-place quicksort 也有回去处理上个 partition剩下来另一半区间的步骤, 也会有整合结果的步骤 (虽然可以不做事), 但就跟递回呼叫类似, 你要用同份程式码执行在不同情境 (context) 下, 先要有办法把情境资讯给储存起来

这个问题也是我现在正在想的，目前的code只能一直往左或是一直往右。中间的小阵列初步的想法是设定两个新的变量存新的边界去跑，不过这边就是要想想怎么写，写出来还要在看看是不是O(nlogn)不过merge sort就比较好找到迭代版本的code

用 LIFO stack 去存当前区间、pivot、阶段就可以了这边有两种实作可以对照看 https://bit.ly/2T2HEOH

如果可以接受多 O(log n) 的空间应该还好写就是了另外其实 divide 有很好懂的写法, 不一定要左右交换

感谢两位的分享，不过我看网络上资料in place的快排才是最快的，其他都比合并排序慢

stack存还没排过的区间

还会是 in-place 呀, Quicksort 本来就要 O(log n) 的堆叠空间实际用的 sorting algorithm 记得都是好几种的混合

stack存还没排过的区间

还会是 in-place 呀, Quicksort 本来就要 O(log n) 的堆叠空间实际用的 sorting algorithm 记得都是好几种的混合

但我看网络上的资料是说不需要另外开阵列给他，而且in place应该也只是阵列内的元素交换而已

那有个问题: 你定义区域变量要不要算进空间复杂度? 你进行递回呼叫算不算配置内存?

我找到的资料。 https://reurl.cc/moQQ7我目前的想法空间复杂度应该只是常数，但我还没实现

再研究一下 in-place algorithm 指的是哪方面的 in-place吧, 如果 quicksort 空间复杂度可以到常数你就可以得奖了

那如果只是单纯在原阵列中排序为何还需要其他空间喔看来是我误会in-place的意思了

那个 O(log n) 是递回的堆叠空间, 在原本的 quicksort就有. 手写堆叠多多少少可以变循环的形式, 而且quicksort 的递回方式很简单, 写出来应该也不会太难懂当然我个人是喜欢写成递回的形式. 递回跟归纳法一样,递回呼叫想成 "由归纳假设", 就可以把阵列排好了

我看过msort的递回确实比迭代简单，qsort递回也蛮好写的，但是个人是喜欢迭代

O(log N) 不是专指递回需要的空间, 而是为了 divide &conquer 需要记住的资讯量, 你用 iterative 因为也要记录相同资讯, 所以免不了这部分的空间复杂度. recursive 只是把资讯存在 call stack 上, 这样的分别而已把递回跟 divide & conquer 划上等号就错了, 应该从了解算法本身着手. divide 我也可以开好多条 thread 去作, 讨论实作根本无助于理解这个 O(log N)hint: O(log N) 跟算法是 top-down 有关你会觉得 iterative merge sort 实作很好理解的原因在于即使用 bottom-up approach 去实作也很容易, 因为边界都可以在一开始的时候全算出来, 但对于 top-down 的算法, 想要把 "分出子问题" 这件事跟 "解决问题本身" 成本相仿, 你如实作出完全循环版, 会发现成本都在储存子问题资讯上面,空间复杂度 O(N log N), 为了蒐集资讯需额外付出时间成本O(N log N)

你说得对

但我看网络上的资料是说不需要另外开阵列给他，而且in place应该也只是阵列内的元素交换而已

那有个问题: 你定义区域变量要不要算进空间复杂度? 你进行递回呼叫算不算配置内存?

我找到的资料。 https://reurl.cc/moQQ7我目前的想法空间复杂度应该只是常数，但我还没实现

再研究一下 in-place algorithm 指的是哪方面的 in-place吧, 如果 quicksort 空间复杂度可以到常数你就可以得奖了

那如果只是单纯在原阵列中排序为何还需要其他空间喔看来是我误会in-place的意思了

那个 O(log n) 是递回的堆叠空间, 在原本的 quicksort就有. 手写堆叠多多少少可以变循环的形式, 而且quicksort 的递回方式很简单, 写出来应该也不会太难懂当然我个人是喜欢写成递回的形式. 递回跟归纳法一样,递回呼叫想成 "由归纳假设", 就可以把阵列排好了

我看过msort的递回确实比迭代简单，qsort递回也蛮好写的，但是个人是喜欢迭代

O(log N) 不是专指递回需要的空间, 而是为了 divide &conquer 需要记住的资讯量, 你用 iterative 因为也要记录相同资讯, 所以免不了这部分的空间复杂度. recursive 只是把资讯存在 call stack 上, 这样的分别而已把递回跟 divide & conquer 划上等号就错了, 应该从了解算法本身着手. divide 我也可以开好多条 thread 去作, 讨论实作根本无助于理解这个 O(log N)hint: O(log N) 跟算法是 top-down 有关你会觉得 iterative merge sort 实作很好理解的原因在于即使用 bottom-up approach 去实作也很容易, 因为边界都可以在一开始的时候全算出来, 但对于 top-down 的算法, 想要把 "分出子问题" 这件事跟 "解决问题本身" 成本相仿, 你如实作出完全循环版, 会发现成本都在储存子问题资讯上面,空间复杂度 O(N log N), 为了蒐集资讯需额外付出时间成本O(N log N)

你说得对