מיון מיזוג
מיזוג הוא איחוד של שתי רשימות או יותר לרשימה אחת.
דוגמא לשימוש במיון מיזוג:
נתונים שני מערכים חד מימדיים.
מערך A עם 10 תאים מסוג שלם ממוין בסדר עולה.
מערך B עם 20 תאים מסוג שלם בסדר עולה.
נכתוב תת תוכנית הממזגת את שני המערכים האלו למערך אחד C ממוין בסדר עולה.
לדוגמא אם נתונים המערכים:
[0,1,7,8,9,10,11,70,99] :מערך A |
[1,3,5,9,11,20,35,36,39] :מערך B |
אזי המערך הממוזג:
[0,1,1,3,5,7,8,9,9,10,11,11,20,35,36,39,70,99] : מערך 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;
·
· קטע הבא אחרי תת תוכנית זו
·
להורדת הפרוצדורה של מיון מיזוג לחץ כאן