מיון אקראי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

תיאור האלגוריתם[עריכת קוד מקור | עריכה]

הדרך שהאלגוריתם ממומש מיוצגת בפסאודו קוד כך:
כל עוד החפיסה לא מסודרת
סדר את החבילה באקראיות

while not isInOrder(deck):
   shuffle(deck)

ריצה וסיום[עריכת קוד מקור | עריכה]

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

ראו גם[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ E. S. Raymond. "bogo-sort". The New Hacker’s Dictionary. MIT Press, 1996.
  2. ^ מקור השם ממשפט הקוף המקליד