מיון מיזוג

מיזוג הוא איחוד של שתי רשימות או יותר לרשימה אחת.

דוגמא לשימוש במיון מיזוג:

נתונים שני מערכים חד מימדיים.

מערך A עם 10 תאים מסוג שלם ממוין בסדר עולה.

מערך B עם 20 תאים מסוג שלם בסדר עולה.

נכתוב תת תוכנית הממזגת את שני המערכים האלו למערך אחד C ממוין בסדר עולה.

לדוגמא אם נתונים המערכים:

אזי המערך הממוזג:

כלומר, מערך C כולל את סכום מספר התאים של מערכים A ו-B ואת כל הערכים של A ו-B כאשר הם ממוינים.

פתרון:

יש שתי דרכים לבצע זאת, הדרך הלא יעילה היא להעתיק את תוכן מערך A למערך C ולאחריו את תוכן מערך B ל- C ואז למיין מחדש את C.

הדרך היעילה היא להשתמש במיון מיזוג כך שלא יהיה צורך למיין את מערך C לאחר המיזוג.

program NAME;
const
   FIRST_A =1; (* Aמספר התא הראשון במערך  *)
   LAST_A =10; (* Aמספר התא האחרון במערך  *)
   FIRST_B =1; (* Bמספר התא הראשון במערך  *)
   LAST_B=20; (* Bמספר התא האחרון במערך  *)
   FIRST_C=1; (* Cמספר התא הראשון במערך  *)
   LAST_C = FIRST_C+(LAST_A-FIRST_A+1)+(LAST_B-FIRST_B+1);
type
   ARRAY_1=array[FIRST_A..LAST_A] of integer;(*A הצהרת  *)
   ARRAY_2=array[FIRST_B..LAST_B] of integer;(*B הצהרת  *)
   ARRAY_3=array[FIRST_C..LAST_C] of integer;(*C הצהרת  *)
         ·       
         ·         קטע הבא לפני תת תוכנית זו
         ·       

procedure MERGER (A:ARRAY_1; B_ARRAY_2; var C:ARRAY_3);
   { תת תוכנית למיזוג שני מערכים }
   (* A -  המערך הראשון למיזוג *)
   (* B -  המערך השני למיזוג *)
   (* var  C – המערך הממוזג  *)
var
   IDX_A: integer; (* A המצביע על התא במערך *)
   IDX_B: integer; (* B המצביע על התא במערך *)
   IDX_C: integer; (* C המצביע על התא במערך *)
begin
   { העמד את המצביעים על התא הראשון בכל מערך }
   IDX_A:=FIRST_A;
   IDX_B:=FIRST_B;
   IDX_C:=FIRST_C;
   {לא הגיע לסוף המערך C בצע את המיזוג כל עוד המצביע של מערך  }
   while IDX_C <= LAST_C do
   begin
         { B קטן מערך במערך A אם מצאת ערך במערך }
      if A[IDX_A] < B[IDX_B] then
      begin
         C[IDX_C]:=A[IDX_A]; (*C העתק תוכן תא זה למערך  *)
         IDX_C:= IDX_C+1; (* C קדם את המצביע במערך *)
         IDX_A:=IDX_A+1; (* A קדם את המצביע במערך *)
               { A אם הגעת לסוף מערך }
         if IDX_A > LAST_A then
              { C למערך B העתק את שארית מערך  }
             while IDX_B <= LAST_B do
             begin
                C[IDX_C]:=B[IDX_B];
                { קדם את המצביעים}
                IDX_C:= IDX_C+1;
                IDX_B:= IDX_B+1;
             end;
        end else  { B אחרת, אם מצאת ערך קטן או שווה במערך }
        begin
          { C העתק ערך זה למערך }
          C[IDX_C]:=B[IDX_B];              
          { קדם את המצביעים}
          IDX_C:= IDX_C+1;
          IDX_B:= IDX_B+1;
          { B אם הגעת לסוף מערך }
          if IDX_B > LAST_B then
             { C למערך A העתק את שארית מערך  }
             while IDX_A <= LAST_A do
             begin
                C[IDX_C]:=A[IDX_A];
                { קדם את המצביעים}
                IDX_C:= IDX_C+1;
                IDX_A:= IDX_A+1;
             end;
        end;
    end;
end;
              ·        
              ·         קטע הבא אחרי תת תוכנית זו
              ·   

 להורדת הפרוצדורה של מיון מיזוג לחץ כאן