快速排序征服方法？ [英] Is Quick Sort a Divide & Conquer approach?

问题描述

1. 我认为合并排序是划分和征服，因为

   
   
   

   / 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）; //（比较/交换）发生在合并 - 征服
     

合并排序跟踪说，该问题被粒化，然后处理，

2. 但是在快速排序中，

   
   
   

   首先， strong>处理（比较/交换）使用分区元素（枢轴）并修复枢轴的最终位置，然后问题大小减半/已分配/分区，

   
   
   

   代码没有给人分歧的印象征服，

     if（hi< = lo）return; 
    int j = partition（a，lo，hi）;你叫这个分割阶段吗？ 
    sort（a，lo，j-1）; //这看起来像分割阶段，因为问题减半
    sort（a，j + 1，hi）; 
     

快速排序跟踪，显示处理已开始在完整的数组上，然后达到粒度级，

问题：

1. 我对 Divide 阶段的理解意味着减少（一半）问题大小。在快速排序中，您是否以分割阶段来考虑处理（比较/交换）数组和分区？




2. 我对征服阶段的理解意味着收集/合并。快速排序，征服阶段是什么意思？

---

 注意：初学者，排序算法
  

解决方案

Divide&征服算法有三个阶段：

1. 分割


2. 征服


3. 合并，

对于合并排序（ http://www.cs.umd.edu/~meesh/351/mount/lectures/lect6-divide -conquer-mergesort.pdf ）：

1. 分割：将数组拆分成2个子阵列，


2. 征服：合并对结果子数组进行递归排序，


3. 合并：将两个排序的子数据合并到一个排序的列表中。

要快速排序（ https://www.cs.rochester.edu/~gildea/csc282/slides/C07-quicksort.pdf ）：

分隔：首先重新排列，然后将阵列分成2个子阵列，

1. 征服：递归地快速排序生成的子数组，


2. Com bine：无。

注意：感谢罗切斯特大学和马里兰大学CS部门。 p>

1. 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 - Conquer
   

Merge sort trace says, that problem is granulated and then processed,

2. 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:

1. 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?

2. 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:

1. Divide,
2. Conquer,
3. Combine,

For merge sort (http://www.cs.umd.edu/~meesh/351/mount/lectures/lect6-divide-conquer-mergesort.pdf):

1. Divide: Split the array into 2 subarrays,
2. Conquer: Merge sort the resulting subarrays recursively,
3. Combine: Merge the two sorted subarrays into a single sorted list.

For quick sort (https://www.cs.rochester.edu/~gildea/csc282/slides/C07-quicksort.pdf):

1. Divide: First rearrange then split the array into 2 subarrays,
2. Conquer: Quick sort the resulting subarrays recursively,
3. Combine: None.

Note: Thanks to University of Rochester and University of Maryland CS departments.

这篇关于快速排序征服方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！