מיון ספגטי

מיון ספגטי הוא אלגוריתם מיון שרץ בזמן ליניארי, שהוצג על ידי אלכסנדר דודני (Alexander Dewdney) בטורו בכתב העת "סיינטיפיק אמריקן". האלגוריתם דורש עיבוד מקבילי.

אלגוריתם

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

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

ניתוח זמן ריצה

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

יש לאחר מכן n מוטות להסרה כשהמוט הארוך ביותר באורך k כך, בהנחה שכל פעולת מגע והסרה אורכת זמן קבוע, מורכבות הזמן הגרוע ביותר של האלגוריתם היא O(n+k).

קישורים חיצוניים

• A. K. Dewdney's homepage
• Implementations of a model of physical sorting, Boole Centre for Research in Informatics
• Classical/Quantum Computing, IFF-Institute