האלגוריתמים הקלאסיים 1 – החלפה (swap)

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

אז היום בסדרה שלנו נתבונן על אלגוריתם ההחלפה – swap.

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

int x = 6, y = 2;

בסיום פעולת ההחלפה היינו רוצים שהמשתנה x יכיל את הערך 2 והמשתנה y יכיל את הערך 6. שימו לב לדרך לא נכונה לבצע את זה –

x = y;

y = x;

שתי שורות ההצבה האילו בעצם מקבילות לניסוח “x מקבל את ערכו של y ו-y מקבל את ערכו של x”. משפט כזה נשמע די הגיוני כשאומרים אותו בעברית, אבל הוא הופך לחסר משמעות כשמתרגמים אותו לשפת תכנות, כיוון שבשפת תכנות הפעולות קורות בסדרתיות, אחת אחרי השניה. כשכותבים משפט כמו

x = y;

אכן מציבים בתוך x את ערכו של y (דהיינו 2 במקרה הזה), אבל כיוון שפעולת ההצבה היא פעולה דורסנית, ערכו הקודם של x נמחק, ולא ניתן לשחזור. המשפט הבא –

y = x;

הוא חסר משמעות כרגע, כיוון שערכו של x הוא 2, וכך גם ערכו של y. לא ביצענו החלפה, אלא הצבה של אותו ערך פעמיים.

איך בכל זאת עושים את זה? כמו שהתמונה למעלה מרמזת, אנחנו צריכים משתנה שלישי, שישמש כמאגר זיכרון זמני. נשמור לתוכו באופן זמני את ערכו של x וכך נוכל לדרוס את הערך שב-x. ואז נוכל לקחת את הערך השמור ולדרוס איתו את ערכו של y –

int temp;

temp = x;

x = y;

y = temp;

שימו לב שבשורה השניה אנחנו מציבים את x בתוך temp, וכך שומרים את ערכו בצד. השורה השלישית מציבה ב-x את y ודורסת אותו, אבל ערכו שמור בצד בתוך temp ולכן בשורה הרביעית אנחנו “משחזרים” את הערך הזה ומציבים אותו ב-y. בסיומו של התהליך ערכי המשתנים התחלפו.

זהו, זה כל האלגוריתם. ה”שילוש הקדוש” הזה, של הצבה זמנית, דריסה, ושחזור, מהווה את אלגוריתם ההחלפה, והוא מופיע בהמון מקומות כחלק מהפעולות היסודיות. למשל – אם נרצה למיין מערך, נרצה לסדר את האיברים שבו בסדר אחר (נניח מהקטן לגדול). מה שאומר שאיברים במערך יצטרכו להחליף מקום, ולכן נשתמש באלגוריתם ההחלפה.

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

x = x+y;

y = x – y;

x = x – y;

אתם מוזמנים לבדוק את זה עם הערכים הראשוניים – x = 6 ו-y=2. כאמור, זה טריק נחמד מחשבתית, אבל אני חושב שלמען הבהירות והקריאות של הקוד עדיף להשתמש בגרסה הקודמת עם משתנה העזר.

וחידה קטנה בשבילכם – את אותו הטריק שעשינו עם פעולות חיבור וחיסור, אפשר לבצע עם פעולות כפל וחילוק, ככה –

x = x * y;

y = x / y;

x = x / y;

תוכלו לבדוק את הקוד עם אותם ערכים x = 6, y = 2 ולראות שהתשובה נכונה, כלומר ערכי המשתנים מתחלפים. ובכל זאת, הפתרון הזה, באמצעות כפל וחילוק, לא נכון לכל המקרים. תוכלו לראות מדוע ולתת דוגמא של ערכי x, y שעבורם האלגוריתם שוגה?