מיון בועות רקורסיבי של מטריצה

נגדיר: מטריצה ממוינת (Sorted Matrix) היא מטריצה (מערך דו-ממדי) מלאה במספרים שלמים, שבה במעבר על המטריצה החל בשורה העליונה ועד לשורה התחתונה, ובכל שורה במעבר משמאל לימין, הערכים במטריצה יהיו ממוינים בסדר עולה מהקטן לגדול. שימו לב שבכל שורה, האיבר האחרון בה קטן או שווה לאיבר הראשון בשורה הבאה.

נתון מערך דו-ממדי (מטריצה) mat המלא במספרים שלמים שאינו ממוין.

כתבו שיטה סטטית רקורסיבית המממשת את אלגוריתם המיון מיון-בועות (bubble sort) על מערך דו-ממדי. השיטה מקבלת מערך דו-ממדי המלא במספרים שלמים, והופכת אותו למערך דו-ממדי ממוין עם המספרים האלו. שימו לב שעליכם לממש דווקא את השיטה מיון-בועות ולא אף שיטת מיון אחרת.

דוגמא: אם השיטה מקבלת את המטריצה הבאה:

	0	1	2	3	4
0	79	18	49	10	80
1	6	45	26	28	84
2	70	93	98	15	29
3	42	97	18	82	79
4	69	80	34	75	18
5	2	49	49	60	77

תוכן המטריצה לאחר הקריאה לשיטה צריך להיות:

	0	1	2	3	4
0	2	6	10	15	18
1	18	18	26	28	29
2	34	42	45	49	49
3	49	60	69	70	75
4	77	79	79	80	80
5	82	84	93	97	98

השיטה שתכתבו צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר שתכתבו (אם תכתבו) לא יכולות להכיל לולאות.

אילוצים:

ניתן להניח שהמערך מלא בנתונים חוקיים ואינו null. אין צורך לבדוק זאת.
ייתכנו ערכים שווים במטריצה.
במהלך הפתרון אין להשתמש במערכי עזר או במבני נתונים נוספים.
השינוי צריך להתבצע ישירות על גבי המטריצה שהשיטה מקבלת כפרמטר.

דוגמה 1:

קלט:

mat =
[[79, 18, 49, 10, 80],
 [6, 45, 26, 28, 84],
 [70, 93, 98, 15, 29],
 [42, 97, 18, 82, 79],
 [69, 80, 34, 75, 18],
 [2, 49, 49, 60, 77]]

פלט:

[2, 6, 10, 15, 18]
[18, 18, 26, 28, 29]
[34, 42, 45, 49, 49]
[49, 60, 69, 70, 75]
[77, 79, 79, 80, 80]
[82, 84, 93, 97, 98]

הסבר: הערכים במטריצה משוכבים באופן אקראי. לאחר המיון כל האיברים ממוינים בסדר עולה (לפי מעבר שורה אחר שורה), כולל ערכים כפולים: 18 מופיע שלוש פעמים, 49 שלוש פעמים, 79 ו-80 פעמיים כל אחד. שימו לב שהאיבר האחרון בכל שורה קטן או שווה לאיבר הראשון בשורה הבאה.

דוגמה 2:

קלט:

mat = [[3, 1, 2]]

פלט:

[1, 2, 3]

הסבר: מטריצה בעלת שורה אחת. המיון מתבצע על השורה כמערך חד-ממדי רגיל.

דוגמה 3:

קלט:

mat =
[[5],
 [4],
 [3],
 [2],
 [1]]

פלט:

[1]
[2]
[3]
[4]
[5]

הסבר: מטריצת עמודה (בכל שורה איבר אחד) הממוינת בסדר הפוך. המיון מעביר כל איבר למקומו הנכון לאורך העמודות.

דוגמה 4:

קלט:

mat =
[[4, 1],
 [2, 3]]

פלט:

[1, 2]
[3, 4]

הסבר: מטריצה ריבועית קטנה. האיבר הגדול ביותר (4) עובר לסוף וכל השאר נדחפים צעד אחד אחורה.

דוגמה 5:

קלט:

mat =
[[1, 2, 3],
 [4, 5, 6]]

פלט:

[1, 2, 3]
[4, 5, 6]

הסבר: המטריצה כבר ממוינת. המיון לא משנה אותה (אף החלפה לא מתבצעת).

דוגמה 6:

קלט:

mat =
[[5, 5, 5],
 [5, 5, 5]]

פלט:

[5, 5, 5]
[5, 5, 5]

הסבר: כל האיברים שווים. אין צורך בהחלפות, והמטריצה נשארת ללא שינוי.

דוגמה 7:

קלט:

mat =
[[-3, 7, 0],
 [-10, 4, -3],
 [9, -1, 2]]

פלט:

[-10, -3, -3]
[-1, 0, 2]
[4, 7, 9]

הסבר: מטריצה עם ערכים שליליים, אפס וערכים כפולים (-3 מופיע פעמיים). המיון מסדר את כל הערכים בסדר עולה.

דוגמה 8:

קלט:

mat = [[42]]

פלט:

[42]

הסבר: מטריצה עם תא אחד בלבד. היא ממוינת מעצם הגדרתה ולכן אין שינוי.

דוגמה 9:

קלט:

mat =
[[9, 8, 7, 6],
 [5, 4, 3, 2],
 [1, 0, -1, -2]]

פלט:

[-2, -1, 0, 1]
[2, 3, 4, 5]
[6, 7, 8, 9]

הסבר: מטריצה ממוינת בסדר יורד, שהוא המקרה הגרוע ביותר לאלגוריתם. כל האיברים מתהפכים.

בינוניהפתוחה – 2026ב', שאלון 468, מועד 98