Indeed. It's amazing just how difficult it is to write a correct in-place quicksort that handles all edge cases. It won't be short and elegant either. Just go ahead and try it.
program qsortTest;
const N = 1000;
var
a: array [0..N] of integer;
i: integer;
procedure quicksort(var a: array of integer; l, r: integer);
var
i, j, temp: integer;
pivot: integer;
begin
pivot := a[(l+r) div 2]; i := l; j := r;
while i < j do
begin
while a[i] < pivot do inc(i);
while a[j] > pivot do dec(j);
if i <= j then
begin
temp := a[i];
a[i] := a[j];
a[j] := temp;
inc(i); dec(j);
end;
end;
if j > l then quicksort(a, l, j);
if i < r then quicksort(a, i, r);
end;
begin
{ populating the array }
for i := 0 to N do
a[i] := random(N);
writeln('initial array');
for i := 0 to N do write(a[i]:6);
writeln;
quicksort(a, 0, N);
writeln;
writeln('sorted array');
for i := 0 to N do write(a[i]:6);
writeln;
end.
Do for loops in delphi/pascal iterate 'up to' or 'up to and including' ?
If they iterate 'up to' then:
It would seem to me that on the initial call to 'quicksort' the '1000' gets passed in to 'r', the value of 'r' then gets passed in to 'j'.
Now if "'a[j]' < p" will refer to the uninitialized value in a[1000] and compare it to p, the first decrement will not take place, i<=j and now the code will swap with a[i] with a[1000].
This should cause the uninitialized value (0?) to end up as the first element in the sorted output array.
I hope I analyzed that correct, I don't have access to a pascal/delphi compiler here.
When you run your code do you see the output starting with a '0' element ?
Is there another element from the input array missing in the output ?
If pascal/delphi loops iterate up-to-and-including did you actually intend to sort an array of 1001 elements ?
