מיון אקראי
במדעי במחשב, מיון אקראי (בנוסף מיון טיפש, מיון איטי[1], מיון קוף[2] ובאנגלית bogosort ) הוא אלגוריתם מיון מאוד לא יעיל המבוסס על ניסוי וטעייה.
האלגוריתם מאוד לא שימושי למיון, אך שימושי למטרות לימוד, לדוגמה השוואה עם אלגוריתמים יותר שימושיים.
אם ננסה למיין חפיסת קלפים על ידי מיון זה היינו בודקים כל פעם אם החפיסה ממוינת, אם לא - נזרוק את החפיסה לאוויר, נרים את הקלפים בסדר אקראי. נחזור על התהליך עד שהחפיסה ממוינת.
תיאור האלגוריתם
[עריכת קוד מקור | עריכה]הדרך שהאלגוריתם ממומש מיוצגת בפסאודו קוד כך:
כל עוד החפיסה לא מסודרת
סדר את החבילה באקראיות
while not isInOrder(deck):
shuffle(deck)
ריצה וסיום
[עריכת קוד מקור | עריכה]בהנחה שכל האיברים שונים, מספר ההשוואות הממוצע ישאף ל ומספר ההחלפות הממוצע יהיה .
הסיבה להפרש בין מספר ההשוואות המצופה למספר ההחלפות המצופה הוא שמגלים שלא כל האיברים ממוינים רק אחרי מספר השוואות, ללא תלות במספר האיברים הכולל, בעוד שמספר ההחלפות תלוי במספר האיברים.
ראו גם
[עריכת קוד מקור | עריכה]הערות שוליים
[עריכת קוד מקור | עריכה]- ^ E. S. Raymond. "bogo-sort". The New Hacker’s Dictionary. MIT Press, 1996.
- ^ מקור השם ממשפט הקוף המקליד
| אלגוריתמי מיון | ||
|---|---|---|
| רקע תאורטי | תורת הסיבוכיות • סימון אסימפטוטי • סדר מלא • רשימה • אלגוריתם תוך-מקומי • מיון יציב | |
| אלגוריתמי מיון | אקראי • בועות • בחירה • בסיס • הכנסה • מהיר • מיזוג • מנייה • מסרק • סלים • ערימה • רשת מיון • שייקר • של | |
| שונות | מיון טופולוגי • בעיית סידור הפנקייקים של גודמן | |