מתחלקים לקבוצות

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

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

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

המטרה היא לסדר מחדש את האיברים בשני “גושים” – גוש אחד יכיל את כל איברי הקבוצה הראשונה (הסדר הפנימי לא משנה) והגוש השני את כל איברי הקבוצה השניה.

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

הנה לדוגמא מערך כזה –

11-1

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

11-2

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

שימו לב – אנחנו לא יודעים מראש כמה איברים יש בכל קבוצה.

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

רעיון האלגוריתם אומר דבר כזה – נשמור שני אינדקסים – start, end. כאשר start יתחיל מאפס (תחילת המערך) ו-end יתחיל מ-7 (במקרה הזה, ובאופן כללי, end ישמור את האינדקס של התא האחרון במערך).

כעת נתחיל לבדוק את המספר שנמצא בתא ה-start. ישנן שתי אפשרויות – או שהמספר שייך לקבוצה הראשונה או שהוא שייך לקבוצה השניה.

אם הוא שייך לקבוצה הראשונה, אזי הוא נמצא כבר במקומו הנכון במערך, ולכן נקדם את start באחד, ונבדוק את התא הבא. אם הוא שייך לקבוצה השניה סימן שהוא לא נמצא במקום הנכון שלו (הוא צריך להיות בצד השני של המערך) ולכן נעצור את הבדיקה כש-start מצביע על האיבר שלא נמצא במקומו, ונתחיל לבדוק מהצד השני.

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

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

בדוגמא שלנו, נתחיל כש-start מצביע על אינדקס 0. המספר באינדקס זה הוא 4, וכיוון שהוא זוגי, אז הוא במקומו, ולכן start מתקדם באחד ומגיע לאינדקס 1. כאן הוא נתקל במספר 5, שאינו במקומו, ולכן נעצור את start ונעבור לבדוק את end, שמתחיל מאינדקס 7. באינדקס זה יש את המספר 6, שהוא זוגי, ולכן הוא צריך להיות בצד השני של המערך. האיור הבא מדגים את המצב –

11-3

והמערך לאחר ההחלפה יראה כך (מודגשים שני הערכים שהוחלפו):

11-4

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

הנה הקוד שעושה את העבודה:

11-5

ומה לגבי זמן הריצה? שימו לב שבכל איטרציה של ה-while החיצוני, ה-while הפנימי הראשון מבצע מספר כלשהו של צעדים עבור start, ואז ה-while הפנימי השני מבצע מספר כלשהו של צעדים עבור end. כל הלולאה נגמרת כאשר שני האינדקסים נפגשים. כלומר, אנחנו לא יודעים מה יהיה סדר ההתקדמות, וכמה צעדים יעשה start וכמה יעשה end, אבל ברור שאם מספר הפעמים שנקדם את start יהיה x, אז מספר הצעדים שנקדם את end יהיה n-x (שוב, n הוא גודל המערך), לכן סך כל הצעדים שמבצעת הלולאה החיצונית הוא n.

האלגוריתם הזה פשוט, ומאוד חזק. נתקלים בו במקומות רבים, אולי הנפוץ שבהם הוא השיטה של מיון מהיר (quicksort) שעושה שימוש באלגוריתם ה-partition כדי לחלק את המערך לאיברים שקטנים ממספר מסויים ולכאלה שגדולים ממנו.

והנה כמה שאלות קטנות למיטיבי לכת –

  • מה לדעתכם יקרה אם המערך במקרה מכיל רק איברים מקבוצה אחת ולא משתיהן? (למשל, בדוגמא שלנו, רק מספרים זוגיים).
  • בקוד עצמו ישנן שתי לולאות while פנימיות שמשכפלות את התנאי ששואלת לולאת ה-while החיצונית. מדוע נדרש השכפול הזה? אתם יכולים לחשוב על דרך קצת יותר אלגנטית לכתוב את הקוד?
  • מה היה קורה אם לא היינו קובעים את תנאי העצירה של האלגוריתם להיות start < end אלא נותנים לאינדקסים להמשיך עד הסוף (כלומר, נותנים ל-start להמשיך עד סוף המערך ול-end להמשיך עד תחילתו)?