0

here is the code to partition in merge sort..am not able to understand actually how does recusrion works in it!!

MERGE SORT PARTITION 

void partition(int arr[], int low, int high){
    int mid;
    if(low < high){
         mid = (low + high)/2;
         partition(arr, low, mid);
         partition(arr, mid + 1, high);
         mergeSort(arr, low, mid, high);
    }
}

actually am getting messed up in many recursive problems and am not able to understand how does system stack works in recursion... am a beginner..

4

2 回答 2

2

I'll try to make recursive functions simpler for you. Take for example a small example of factorial pseudo-code:

int fact(n)
{
  if(n==1 || n==0) return 1;
  else
  return (n*fact(n-1));
}

What this will do is create a stack of functions. Suppose I call fact(3) this will make a stack like:

fact(0)
fact(1)
fact(2)
fact(3)

where each function is pushed into the stack. First fact(3) is called. fact(3) calls fact(2). So after the passes --

Stack build up:

                                               fact(0)
                                   fact(1)     fact(1)
                       fact(2)     fact(2)     fact(2)
empty --> fact(3) ---> fact(3) --> fact(3) --> fact(3)

Now the function catches n=0 and returns 1. Now the functions start popping out.

Stack :

   fact(0) -----> (returns 1) = 1
                    fact(1) -----> (returns 1) * 1 (1's popped out)
                                     fact(2) -----> (returns 2) * 1 (1 is actually 1*1)
                                                      fact(3) -----> (returns 3) * (2 = 2*1*1)
                                                                                          ----->6

EDIT:Added pop functionally. As for the sorting stack kindly check out @P0W's answer.

Trying taking a small example and build your stack. Then move onto complex ones. Remember practice is the key. This is how recursive functions work as a stack.

Hope it helps. :)

于 2013-08-24T16:41:23.820 回答
1

让我们举个例子

数组arr ={ 5,2,4,7,1,3,2,6};8 个元素

                            1 2 3 4 5 6 7
                                  ^(partition+mergeSort)
                                  |  
                    +------------+ +---------------+
                    |                              |
                2 4 5 7                          1 2 3 6
                    ^   (partition+mergeSort)        ^ (partition+mergeSort)  
                    |                              |
                +--+ +---+                     +--+ +---+
                |        |                     |        |
               2  5     4  7                 1   3     2  6
                     ^ (partition+mergeSort)          ^  (partition+mergeSort) 
                     |                              | 
                +---+ +---+                    +---+ +---+
                |         |                    |         |
              5   2     4   7                1  3      2   6 
                 4 elements                      4 elements 

                          Initial Unsorted Array

从下到上，形成两个数组

arr[low...mid]在每个递归调用中， arr[mid+1...high]最后它们都被合并了。

只要low<high

它只是一个如何mergeSort在这里工作的示例，您可以按照此示例的代码进行操作。

partition(arr, 0,7)对这个未排序数组的调用将具有：

在第一遍mid =3 arr被分成两部分使用

partion(arr,0,3)和partion(arr,4,7)

这些分区中的每一个都再次被分成两部分，即 0 到 3 被分成(0,1)& (2,3)，再进一步(0,1)和(1,1)。(1,1)被跳过，因为low > high这最后 2 个元素与mergeSort

然后，一组这样的小排序数组最终合并起来，因为它在随后的遍历中退出递归。

这在这里有点难以解释，用文本格式，在纸上尝试一下，我相信你可以弄清楚，使用更小的数组，比如 4 个元素。

于 2013-08-24T16:29:26.343 回答