Why this quicksort implementation gives correct output instead of garbage value?

Question

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.

There is no requirement for incorrect code to give a seg fault. It will if it breaks something. — Weather Vane, Jun 04 '23 at 16:43
Going out of bounds of arrays or allocated memory leads to *undefined behavior*. — Some programmer dude, Jun 04 '23 at 16:44
But why does it give correct output? wouldn't it swap the array element with some garbage value when i goes out of array limit? — SnowPuff, Jun 04 '23 at 16:48
@WeatherVane: There is no requirement in the C standard that “incorrect” code cause a segmentation fault. There are requirements in various operating systems that “incorrect” code, by specification of the operating system, give a segmentation fault. Such faults are critical for security and other purposes. — Eric Postpischil, Jun 04 '23 at 16:48
@EricPostpischil But why would it give correct ouput? why wouldn't it go out of bounds and swap array elements with some garbage values? — SnowPuff, Jun 04 '23 at 16:50
_"why does it give correct output?"_ - It _may_ give the correct output. Since using this function makes the program have undefined behavior, it could give just about any or no output. — Ted Lyngmo, Jun 04 '23 at 16:50
@EricPostpischil I think that was covered by "if it breaks something." — Weather Vane, Jun 04 '23 at 16:52
Does this answer your question? [How dangerous is it to access an array out of bounds?](https://stackoverflow.com/questions/15646973/how-dangerous-is-it-to-access-an-array-out-of-bounds) — Tom Karzes, Jun 04 '23 at 16:56
Re “wouldn't it swap the array element with some garbage value when i goes out of array limit?”: When `i` is out of bounds and `a[i] — Eric Postpischil, Jun 04 '23 at 16:56
… If the values in the range are 1, 2, 3, 4, and 5, in any order, and the values just beyond the array are 99 and 3124, a sort will not swap the later values into the array. — Eric Postpischil, Jun 04 '23 at 16:56
@WeatherVane: That is a semantically null statement. It is only meaningful for somebody who already knows the details of out segmentation faults work, in which case it gives them no information because they already have it, and it is meaningless for a student who does not know how segment faults work and what “breaks something” means, because it does not give them any information because it does not define “breaks something.” — Eric Postpischil, Jun 04 '23 at 16:58
@EricPostpischil if my statement was meaningless, then so was yours, since you have not stated what "incorrect" behaviour you are talking about, which the OS will react unfavourably to. I was merely pointing out to OP that a segmentation fault isn't a *necessary* result of the code. Have a nice day. — Weather Vane, Jun 04 '23 at 17:02
@WeatherVane: Re “so was yours”: Sure, my statement did not explain what “incorrect” behavior with respect to the operating system was, because it was not a statement directed at a student learning this. It was explaining to you why your statement was not sufficient to teach a student, and you already know how memory mapping behaves. — Eric Postpischil, Jun 04 '23 at 17:08
@SnowPuff "Shouldn't that give segmentation error?" --> No. It might, might not. Programming C is like walking a [tight-rope](https://en.wikipedia.org/wiki/Tightrope_walking) without a net. C is not required to not emit extra code to see if you fall off. Good luck. — chux - Reinstate Monica, Jun 04 '23 at 20:09

Eric Postpischil · Answer 1 · 2023-06-04T18:23:23.913

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.

where can I find and learn more about this behaviour of reversing the outofbound swap? Thanks for the answer — SnowPuff, Jun 04 '23 at 17:10
@SnowPuff *where can I find and learn more about this behaviour of reversing the outofbound swap?* **Your** code is doing it. — Andrew Henle, Jun 04 '23 at 18:06

Why this quicksort implementation gives correct output instead of garbage value?

1 Answers1