英文:
Why this quicksort implementation gives correct output instead of garbage value?
问题
在这个快速排序的代码中，如果输入数组是递减的，例如 5 4 3 2 1，变量 i 会不断增加而没有进行检查，并且越界。这难道不应该导致分段错误吗？正如回复中指出的那样，即使它不会导致分段错误，为什么它不会将 arr[j] 与 arr[i] 中的垃圾值进行交换（其中 i 超出了边界）？
int HoarePartition(int a[],int l,int r)
{
int p,i,j,temp;
p=a[l],i=l,j=r+1;
do
{
do
{
i++;
}while(a[i]<p);
do
{
j--;
}while(a[j]>p);
temp=a[i];
a[i]=a[j];
a[j]=temp;
}while(i<j);
temp=a[i];
a[i]=a[j];
a[j]=temp;
temp=a[l];
a[l]=a[j];
a[j]=temp;
return j;
}
这个与快速排序函数一起，可以正确对输入数组 5 4 3 2 1 或类似递减数组进行排序。
英文:
In this code for quicksort, if input array is decreasing, for example 5 4 3 2 1 , variable i goes on incrementing without check and go out of array bound. Shouldn't that give segmentation error? As pointed out in replies, even if it doesnt give segmentation fault, why doesn't it swap arr[j] with garbage value in arr[i](where i is out of bounds)?
int HoarePartition(int a[],int l,int r)
{
int p,i,j,temp;
p=a[l],i=l,j=r+1;
do
{
do
{
i++;
}while(a[i]<p);
do
{
j--;
}while(a[j]>p);
temp=a[i];
a[i]=a[j];
a[j]=temp;
}while(i<j);
temp=a[i];
a[i]=a[j];
a[j]=temp;
temp=a[l];
a[l]=a[j];
a[j]=temp;
return j;
}
This along with quicksort function gives correct sorted array for input array of 5 4 3 2 1 or similar decreasing array.
答案1
得分: 4
不会。分段错误并未指定用于捕捉超出进程内个别数组或其他对象边界的错误。它们被指定在具有它们的操作系统上捕捉对进程权限不正确的内存访问错误，比如尝试读取进程具有读取权限但超出内存边界的内存，尝试写入进程具有写入权限但超出内存边界的内存，或者尝试执行进程具有执行权限但超出内存边界的指令。
当一个进程拥有两个数组a和b时，通过使用超出a的i读取a[i]，进入b，不会生成分段错误，因为进程有权读取b。当一个进程在为其堆栈分配（和映射）的内存中有一个数组a时，通过使用超出a但仍在其堆栈空间内的i读取a[i]，也不会生成分段错误。
立刻在do循环内交换a[i]和a[j]之后，该例程立刻将它们交换回来，撤销了更改。这是因为一旦i超出了边界，i<j为假，因为j从r+1开始递减，所以我们知道它在边界内，因此小于i。因此，带有while(i<j)的循环终止，然后执行它之后的代码，该代码交换a[i]和a[j]。
所以，只要没有发生分段错误，与数组外部元素的任何交换都会立刻撤销，没有持久影响。
英文:
> Shouldn't that give segmentation error?
No. Segmentation faults are not specified to catch errors of going outside bounds of individual arrays or other objects within a process. They are specified, on operating systems that have them, to catch errors of accessing memory with incorrect permissions for the process, such as attempting to read outside the bounds of memory the process has permission to read, attempting to write outside the bounds of memory the process has permission to write, or attempting to execute instructions outside the bounds of memory the process has permission to execute.
When a process has two arrays, a and b, then reading a[i] with an i that extends outside of a into b will not generate a segmentation fault, because the process has permission to read b. When a process has an array a in the memory allocated (and mapped) for its stack, then reading a[i] with an i that extends outside of a but is still within its stack space will not generate a segmentation fault.
> Why does the code give correct output?
Immediately after swapping a[i] and a[j] inside the do loop, the routine immediately swaps them back, reversing the change. This is because, once i is out of bounds, i<j is false, because j starts at r+1 and is decremented, so we know it is in bounds and hence is less than i. So the loop with while(i<j) terminates, and the code immediately after it, which swaps a[i] and a[j], is executed.
So, as long as no segment fault occurs, any swap with an element outside of the array is immediately reversed and has no lasting effect.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论