证明正确的，并征服排序

假设我们有一个排序方法：证明正确的，并征服排序

void DD_sort(int a[], int x, int y, int size_a) 
{ 
    if(x == y){ 
     return; 
    } 
    else if(y == x+1){ 
     if(a[x] > a[y]){ 
     /* swap the content */ 
     return; 
     } 
    } 
    else{ 
     int s = floor((y+1-x)/3); 
     DD_sort(a, x, y-s, s); 
     DD_sort(a, x+s, y, s); 
     DD_sort(a, x, y-s, s); 
    } 
}

我们可以用什么方法来证明排序算法正确或不正确排序数组？有没有系统的方法解决这个问题？我知道它适用于size_a == 1和size_a == 2的情况，但如果size_a是，比如说30，那么我们递归调用大小为数组的2/3大小的排序方法。它看起来好像是有效的，但我不确定如何正式表明这一点。

来源

2014-09-22 Bob John

给x和y的初始值是多少？ – 2014-09-22 00:54:58

@EmanuelePaolini他们是x = 0和y = size_a-1 – 2014-09-22 00:55:50

什么是'size_a'？当它在函数的任何地方没有被真正使用时，它作为参数的目的是什么？ – AnT 2014-09-22 00:56:16

你必须证明这些线

DD_sort(a, x, y-s, s); 
    DD_sort(a, x+s, y, s); 
    DD_sort(a, x, y-s, s);

从X到Y的整个阵列，因为这三个调用将正确地排序数组的给定的子集进行排序。三次调用中的最后一次确保从x到y-s的元素被排序。第二次调用确保从y-s到y的元素被排序。为了得出结论，所有元素都是有序的，你需要证明从y-s到y的元素大于从x到y-s的元素。

这是真实的，因为：第一次调用确保较大的s元素将超出索引y-s-s> = x + s。所以第二次调用会将它们发送到数组的末尾。

如果数组的长度恰好是3 * s，所有的推理都是正确的。如果s小于三分之一的长度，它仍然是正确的，事实上，如果s越小，排序的子集越大。

来源

2014-09-22 01:10:01

证明正确的，并征服排序

回答

相关问题