我认为合并排序是划分和征服,因为
/ strong> - 数组字面上划分为不需要任何处理的子数组(比较/交换),问题大小减半/已分配/ ....
Conquer - merge() 处理的这些子数组(/比较/交换)
代码给人的印象是它是Divide& Conquer,
if(hi < = lo)return; int mid = lo +(hi-lo)/ 2; //否(比较/交换)元素之前分配 sort(a,aux,lo,mid); //问题减半(Divide) sort(a,aux,mid + 1,hi); merge(a,aux,lo,mid); //(比较/交换)发生在合并 - 征服
合并排序跟踪说,该问题被粒化,然后处理,
但是在快速排序中,
首先, strong>处理(比较/交换)使用分区元素(枢轴)并修复枢轴的最终位置,然后问题大小减半/已分配/分区,
代码没有给人分歧的印象征服,
if(hi< = lo)return; int j = partition(a,lo,hi);你叫这个分割阶段吗? sort(a,lo,j-1); //这看起来像分割阶段,因为问题减半 sort(a,j + 1,hi);
快速排序跟踪,显示处理已开始在完整的数组上,然后达到粒度级,
问题:
我对 Divide 阶段的理解意味着减少(一半)问题大小。在快速排序中,您是否以分割阶段来考虑处理(比较/交换)数组和分区?
我对征服阶段的理解意味着收集/合并。快速排序,征服阶段是什么意思?
注意:初学者,排序算法
解决方案
Divide&征服算法有三个阶段:
对于合并排序( www.cs.umd.edu/~meesh/351/mount/lectures/lect6-divide -conquer-mergesort.pdf ):
要快速排序( www.cs.rochester.edu/~gildea/csc282/slides/C07-quicksort.pdf ):
分隔:首先重新排列,然后将阵列分成2个子阵列,注意:感谢罗切斯特大学和马里兰大学CS部门。 p>
I consider Merge sort as divide and conquer because,
Divide - Array is literally divided into sub arrays without any processing(compare/swap), and the problem sized is halved/Quartered/....
Conquer - merge() those sub arrays by processing(compare/swap)
Code gives an impression that it is Divide&Conquer,
if(hi <= lo) return; int mid = lo + (hi-lo)/2; //No (compare/swap) on elements before divide sort(a, aux, lo, mid); // Problem is halved(Divide) sort(a, aux, mid+1, hi); merge(a, aux, lo, mid); // (Compare/swap) happens here during Merge - ConquerMerge sort trace says, that problem is granulated and then processed,
But in Quick sort,
Firstly, Complete array is processed(compare/swap) using a partition element(pivot) and fix the final position of pivot, and then problem size is halved/Quartered/.... for re-partitioning,
Code does not give an impression of divide & conquer,
if(hi <= lo) return; int j = partition(a, lo, hi); // Do you call this divide phase? sort(a, lo, j-1); // This looks like divide phase, because problem is halved sort(a, j+1, hi);Quick sort trace, shows that processing is started on complete array and then reaches granular level,
Questions:
My understanding of Divide phase mean, reducing(half) the problem size. In Quick sort, do you consider processing(compare/swap) array and partition using pivot, as Divide phase?
My understanding of Conquer phase mean, gathering/merging back. In quick sort, Where does conquer phase mean?
Note: Am a beginner, in sorting algorithms
解决方案
Divide & Conquer algorithms have 3 stages:
For merge sort (www.cs.umd.edu/~meesh/351/mount/lectures/lect6-divide-conquer-mergesort.pdf):
For quick sort (www.cs.rochester.edu/~gildea/csc282/slides/C07-quicksort.pdf):
Note: Thanks to University of Rochester and University of Maryland CS departments.
更多推荐
快速排序征服方法?
发布评论