4
\$\begingroup\$

The purpose of the code is to merge two ordered lists (list 1 : 5 integers, list 2 : 8 integers) into another third ordered list, whilst maintaining their order, while entries that appear in more than one list also appear multiple times in the result.

Example:

An input of List1 (Feld1): 3 6 7 9 10, merged with an input of List2(Feld2): 2 7 11 12 15 17 20 21 would result into a third list(Ergebnisfeld) of: 2 3 6 7 7 9 10 11 12 15 17 20 21.

This code works well on my computer, but since I am pretty new to this, I would like to ask, if this is:

  1. The most efficient way to do this (e.g. is the combination of a while and a repeat/until loop the best code for this, or is a for loop better)
  2. If there are any problems with the code, which I am too inexperienced to see, but which might cause me problems later

 program merge (input, output);
    { Reads two ordered lists of integers keyed in by the user, and merges 
them into a third ordered list, without checking their order. 
    if the input is not sorted, the result will be undefined.}

const
  FELDLAENGE1 = 5;
  FELDLAENGE2 = 8;
  ERGEBNISFELDLAENGE = 13; { FELDLAENGE1 + FELDLAENGE2}

type
  tFeld1 = array [1..FELDLAENGE1] of integer;
  tFeld2 = array [1..FELDLAENGE2] of integer;
  tErgebnisFeld = array [ 1..ERGEBNISFELDLAENGE] of integer;

var
  Feld1 : tFeld1;
  Feld2 : tFeld2;
  ErgebnisFeld : tErgebnisFeld;
  i : integer;
  j : integer;
  k : integer;
begin
  { read ordered lists (Felder) }
  writeln (' Please key in', FELDLAENGE1:2, ' values in ascending order for 
the first list. ');
  for i := 1 to FELDLAENGE1 do
      readln (Feld1[i]);
  writeln (' Please key in', FELDLAENGE2:2, ' values in ascending order for 
the second list. ');
  for j := 1 to FELDLAENGE2 do
      readln (Feld2[j]);
  { Merge Feld1 and Feld2 into ErgebnisFeld}
  i :=1;
  j :=1;
  k := 1;

  while (i <= FELDLAENGE1) and (j <= FELDLAENGE2) do
        if Feld1[i] <= Feld2[j] then
           begin
           ErgebnisFeld[k] := Feld1[i];
           i := i+1;
           k := k+1
          end
        else
        begin
          ErgebnisFeld[k] := Feld2[j];
          j := j +1;
          k := k +1
        end;
  { add remaining values to ErgebnisFeld}
  if i > FELDLAENGE1 then
     repeat
           ErgebnisFeld[k] := Feld2[j];
           j := j + 1;
           k := k + 1
     until k = ERGEBNISFELDLAENGE+1
  else
      repeat
            ErgebnisFeld[k] := Feld1[i];
            i := i + 1;
            k := k + 1
      until k = ERGEBNISFELDLAENGE+1;


  writeln ('The merged list is: ');
  for k := 1 to ERGEBNISFELDLAENGE do
      write (ErgebnisFeld[k], ' ');
  writeln;
  readln;

end.
\$\endgroup\$
2
\$\begingroup\$

First, I think you might separate the input/output part from processing data by enclosing the merging routine in a separate procedure. Then the merging procedure can be reused in many places of your programs. And if you move it to a separate unit you'll be able to reuse it in other programs, too, if necessary.

 program merge (input, output);
    { Reads two ordered lists of integers keyed in by the user, and merges 
    them into a third ordered list, without checking their order. 
    if the input is not sorted, the result will be undefined.}

const
  FELDLAENGE1 = 5;
  FELDLAENGE2 = 8;
  ERGEBNISFELDLAENGE = 13; { FELDLAENGE1 + FELDLAENGE2}

type
  tFeld1 = array [1..FELDLAENGE1] of integer;
  tFeld2 = array [1..FELDLAENGE2] of integer;
  tErgebnisFeld = array [ 1..ERGEBNISFELDLAENGE] of integer;

procedure mergeTwoArrays( var Feld1 : tFeld1; var Feld2 : tFeld2;
                          var ErgebnisFeld : tErgebnisFeld)
    var
        i : integer;
        j : integer;
        k : integer;
    begin
        i := 1;
        j := 1;
        k := 1;

        while (i <= FELDLAENGE1) and (j <= FELDLAENGE2) do
            if Feld1[i] <= Feld2[j] then
              begin
                ErgebnisFeld[k] := Feld1[i];
                i := i + 1;
                k := k + 1
              end
            else
              begin
                ErgebnisFeld[k] := Feld2[j];
                j := j + 1;
                k := k + 1
              end;
        { add remaining values to ErgebnisFeld}
        if i > FELDLAENGE1 then
            repeat
               ErgebnisFeld[k] := Feld2[j];
               j := j + 1;
               k := k + 1
            until k = ERGEBNISFELDLAENGE+1
        else
            repeat
                ErgebnisFeld[k] := Feld1[i];
                i := i + 1;
                k := k + 1
            until k = ERGEBNISFELDLAENGE+1;
    end;

var
  Feld1 : tFeld1;
  Feld2 : tFeld2;
  ErgebnisFeld : tErgebnisFeld;
  i : integer;
  j : integer;
begin
  { read ordered lists (Felder) }
  writeln (' Please key in', FELDLAENGE1:2, ' values in ascending order for the first list. ');
  for i := 1 to FELDLAENGE1 do
      readln (Feld1[i]);
  writeln (' Please key in', FELDLAENGE2:2, ' values in ascending order for the second list. ');
  for j := 1 to FELDLAENGE2 do
      readln (Feld2[j]);

  { Merge Feld1 and Feld2 into ErgebnisFeld}
  mergeTwoArrays( Feld1, Feld2, ErgebnisFeld);

  { output results from ErgebnisFeld}
  writeln ('The merged list is: ');
  for k := 1 to ERGEBNISFELDLAENGE do
      write (ErgebnisFeld[k], ' ');
  writeln;
  readln;

end.

Another change I would make is simplifying the code to append input lists' tails in the final part of merge – you can do that with two separate while loops, similar to the main merging loop. Exactly one of them will do the actual work, and the cost of not entering the other one equals the cost of the conditional (if-then-else) in your version.

      { add remaining values from Feld1 to ErgebnisFeld}
      while i <= FELDLAENGE1 do
          begin
              ErgebnisFeld[k] := Feld1[i];
              i := i + 1;
              k := k + 1
          end;

      { add remaining values from Feld2 to ErgebnisFeld}
      while j <= FELDLAENGE2 do
          begin
              ErgebnisFeld[k] := Feld2[j];
              j := j + 1;
              k := k + 1
          end;

Then you may use open arrays to make the routine more generic, so it could merge arrays of arbitrary lenghts, not just 5 plus 8.

You can also explicitly pass the lengths of both input lists as parameters to the routine, so it can merge lists shorter than arrays in which the're stored.

procedure mergeTwoArrays( var Feld1 : array of integer; feldLange1 : integer;
                          var Feld2 : array of integer; feldLange2 : integer;
                          var ErgebnisFeld : array of integer)
    var
        i, j, k : integer;
    begin
        i := 0;    { indices of open arrays start from 0 }
        j := 0;    { and end at length-1 }
        k := 0;

        { merge Feld1 and Feld2 to ErgebnisFeld until one of them becomes empty}
        while (i < feldLange1) and (j < feldLange2) do { note the comp. operator }
            if Feld1[i] <= Feld2[j] then
              begin
                ErgebnisFeld[k] := Feld1[i];
                i := i + 1;
                k := k + 1
              end
            else
              begin
                ErgebnisFeld[k] := Feld2[j];
                j := j + 1;
                k := k + 1
              end;

        { add remaining values from Feld1 to ErgebnisFeld}
        while i < feldLange1 do
            begin
                ErgebnisFeld[k] := Feld1[i];
                i := i + 1;
                k := k + 1
            end;

        { add remaining values from Feld2 to ErgebnisFeld}
        while j < feldLange2 do
            begin
                ErgebnisFeld[k] := Feld2[j];
                j := j + 1;
                k := k + 1
            end;
    end;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.