שאלת מבחן במבוא למדעי המחשב - האוניברסיטה הפתוחה 2012 - רשימות מקושרות

נתונה המחלקה IntNodeTwo הבאה, המייצגת איבר ברשימה מקושרת דו-סטרית המכילה מספרים שלמים: ```java public class IntNodeTwo { private int _num; private IntNodeTwo _next, _prev; public IntNodeTwo(int n) { _num = n; _next = null; _prev = null; } public IntNodeTwo(int num, IntNodeTwo n, IntNodeTwo p) { _num = num; _next = n; _prev = p; } public int getNum() { return _num; } public IntNodeTwo getNext() { return _next; } public IntNodeTwo getPrev() { return _prev; } public void setNum(int n) { _num = n; } public void setNext(IntNodeTwo node) { _next = node; } public void setPrev(IntNodeTwo node) { _prev = node; } } ``` נתונה רשימה מקושרת **דו-סטרית**, הממומשת בעזרת המחלקה IntListTwo, ובה השיטה secret: ```java public void secret() { IntNodeTwo p1 = null; IntNodeTwo p2 = _head; IntNodeTwo p3 = null; int temp; do { if (p2.getNum() == 0) p2 = p2.getNext(); else if (p2.getNum() < 0) { if (p1 == null) p1 = _head; else p1 = p1.getNext(); temp = p1.getNum(); p1.setNum(p2.getNum()); p2.setNum(temp); p2 = p2.getNext(); } else { // p2.getNum() > 0 if (p3 == null) p3 = _tail; else p3 = p3.getPrev(); temp = p3.getNum(); p3.setNum(p2.getNum()); p2.setNum(temp); } } while ((p2 != p3) && p3.getNext() != p2); } ``` מה מבצעת השיטה secret באופן כללי? הסבירו בקצרה **מה** השיטה עושה ולא **כיצד** היא מבצעת זאת.

רמז: שימו לב לשלושת המצביעים: p1 מטפל בשליליים (מתחילת הרשימה), p3 בחיוביים (מסוף הרשימה), ו-p2 סורק. זה דומה לבעיית הדגל ההולנדי.

פתרון: השיטה **secret** מבצעת **מיון הולנדי (Dutch National Flag)** על הרשימה המקושרת הדו-סטרית: היא מסדרת את האיברים כך שכל המספרים **השליליים** יופיעו בתחילת הרשימה, אחריהם כל ה**אפסים**, ולבסוף כל המספרים **החיוביים** בסוף הרשימה. **שימו לב**: הסדר הפנימי בתוך כל קבוצה (שליליים, אפסים, חיוביים) **אינו** בהכרח שמור — השיטה לא ממיינת את הערכים בתוך כל קבוצה, אלא רק מפרידה בין שלוש הקבוצות.