מחפש שיטה למיון מספרים (אלוגריתמים או משהו)

אם למשל יש לי את המספרים 16,22,0,2,7

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

בבקשה:

אלגוריתמי מיון

הכי פשוטים הם מיון בחירה ומיון בועות.

הכי מהיר:

Quick Sort:

http://en.wikipedia.org/wiki/Quicksort

בהצלחה.

הכי מהיר:

Quick Sort:

http://en.wikipedia.org/wiki/Quicksort

בהצלחה.

זה לא תמיד נכון...

Quick sort הוא לא ה SORT הכי מהיר והוא גם ריקורסיבי ויש לו סיבוכיות N log N כמו רוב ה sorts היעילים יחסית. למרות זאת הוא יכול להיות פתרון טוב .

הכי מהיר הוא counting sort שיש לו סיבוכיות N אבל טווח המספרים צריך להיות קבוע וקטן . אם הטווח גדול מדי אפשר להשתמש בradix sort שאומר שממינים את המספרים בחלקים . למשל אם יש לי טווח מספרים מ0 עד 99 אני יכול למין את המספרים לפי האחדות ואז לפי העשרות ואז המספרים יהיו ממוינים.

לאורך זמן Quick Sort הוא הכי מהיר. (כל עוד לא ידוע מה גודל המערך או מספר המשתנים למיון)

אין מה להתווכח על זה... N Log N. זה זמן הריצה המינימלי (לאורך זמן) הדרוש למיין מערך בגודל N.

האלגוריתמים היציבים (כמו counting/radix) הם לא כללים ומסתמכים על עוד מידע נתון בניגוד לאלגורתמים השואתים (כמו quicksort ו bublesort) שמסתמכים רק על אופרטור השוואה בין 2 אלמנטים ברשימה. המידע הנוסף הזה הוא זה שמאפשר לרדת מחסם ה NlogN.

כפי שרשום, היתרון של QuickSort הוא שאפשר לממש אותו ביעילות למעבדים. החיסרון שלו הוא שבפועל אפשר לייצר סידרת קלט שתגרום לו במקרה הגרוע לעבוד בסיבוכיות של N^2.

מנגד, אלגוריתם מיון כמו HeapSort מבטיח תמיד למיין בחסם NlogN (אם כי בפועל הוא לרוב קצת יותר איטי מ QS).

אין מה להתווכח על זה... N Log N. זה זמן הריצה המינימלי (לאורך זמן) הדרוש למיין מערך בגודל N.

זה פשוט לא נכון

O(nlog(n) זה החסם לזמן הריצה שדרוש למיון שמבוסס על השוואות במקרה הכללי.

בהרבה מקרים יש לך מידע נוסף שמאפשר לך לעשות את המיון יותר מהר, למשל (כמו שנאמר קודם) radix sort, שפועל ב- O(n).

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

לטעמי הכי פשוט הוא הbubble sort...אבל צריך לשים את הערכים(המספרים במערך)

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

נו ומה היעלות של האלגוריתם וגם כן לא הבנתי מתי הוא מסתיים בדיוק?

בהחלט יכול להיות מצב שתיהיה לולאה אין סופית(אם משתמשים בלולאה)...

חחח

מעניין אם זה יעיל יותר עבור קלטים עצומים.

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

(אבל זה תלוי במספר המופעים של הפרמוטציות השונות).

ד"א אם משתמשים ביוצר מספרים רנדומלים אמיתי (לא כמו שיש במחשבים) אזי מובטח שכל האלגוריתמים האלו יסתיימו על פי משפט הקוף המקליד:

http://he.wikipedia.org/wiki/%D7%9E%D7%A9%D7%A4%D7%98_%D7%94%D7%A7%D7%95%D7%A3_%D7%94%D7%9E%D7%A7%D7%9C%D7%99%D7%93

טוב זה בהחלט חידוש(בשבילי לפחות) הקוף המקליד...