Im currently trying to make a binary insert program, it reads a random number and inserts it in a sorted list, but every time I execute the program it just returns a list full of 0's I had this problem too when creating a normal insertion one. Even before sorting the list is full of 0's (aka no elements are ever assigned for some reason)
Here's the code:
program BinaryInsert;
function binaryfind(head, tail : integer; e : integer; vector: array of integer) : integer; //uses binary search to find the right placement for e (element) inside the vector
var
mid : integer;
begin
mid := (head + tail) div 2; //keep in mind that div returns the value rounded down
if head <> tail then
begin
if vector[mid] >= e then //>= garantees that this sorting method is stable
binaryfind(mid+1, tail, e, vector)
else
binaryfind(head, mid, e, vector);
end
else
begin
if e >= vector[mid] then
binaryfind := mid + 1 //it should take the place in front of mid (again >= garantees stability)
else
binaryfind := mid; //it should take the place before mid
end;
end;
procedure swap(e1, e2: integer);
var
aux : integer;
begin
aux := e1;
e1 := e2;
e2 := aux;
end;
procedure binaryinsert(e : integer; vector : array of integer); //actual sorting happens here
var
i, placement, l : integer;
begin
l := Length(vector);
placement := binaryfind(0, l-1, e, vector);
vector[l] := e;
for i := (l-1) downto (placement + 1) do
swap(vector[i], vector[i-1]); //reorganizes the array until the new element is at the correct placement
end;
procedure randomsorted(vector : array of integer); //creates a sorted array with n random numbers
var
i : integer;
begin
for i := 0 to Length(vector)-1 do
binaryinsert(random(9999), vector);
end;
var
vector : array of integer ;
e : integer;
begin
SetLength(vector, 5);
randomsorted(vector);
for e in vector do
writeln(e);
readln(e);
end.
I was trying to get a list of sorted random integers
Some observations: the call to random(9999);
without a previous call to Randomize()
always returns 0 as the first value in my test. For a true (semi)random series you should call Randomize()
at beginning of the program.
However, during development, it might be useful to feed selected constant values, just to verify that the sorting works as it should.
Pay attention to the difference between Value
and Variable
parameters. You are passing vector
in two places as a value parameter, but you want to retain the changes you do to the array, ergo, you should pass vector
as a variable parameter.
Finally it seems binaryinsert()
and binaryfind()
need some attention. You are assigning new values to vector[l]
, which is past the end of the array. There might be other problems too.