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