פורסם 2007 בפברואר 2218 שנים אם למשל יש לי את המספרים 16,22,0,2,7מחפש שיטה (לא חייב בשפה ספציפית אלא רק רעיון) לסדר את המספרים לפי הגודל כמובן.
פורסם 2007 בפברואר 2218 שנים הכי מהיר:Quick Sort:http://en.wikipedia.org/wiki/Quicksortבהצלחה.זה לא תמיד נכון...Quick sort הוא לא ה SORT הכי מהיר והוא גם ריקורסיבי ויש לו סיבוכיות N log N כמו רוב ה sorts היעילים יחסית. למרות זאת הוא יכול להיות פתרון טוב .הכי מהיר הוא counting sort שיש לו סיבוכיות N אבל טווח המספרים צריך להיות קבוע וקטן . אם הטווח גדול מדי אפשר להשתמש בradix sort שאומר שממינים את המספרים בחלקים . למשל אם יש לי טווח מספרים מ0 עד 99 אני יכול למין את המספרים לפי האחדות ואז לפי העשרות ואז המספרים יהיו ממוינים.
פורסם 2007 בפברואר 2218 שנים לאורך זמן Quick Sort הוא הכי מהיר. (כל עוד לא ידוע מה גודל המערך או מספר המשתנים למיון)אין מה להתווכח על זה... N Log N. זה זמן הריצה המינימלי (לאורך זמן) הדרוש למיין מערך בגודל N.
פורסם 2007 בפברואר 2218 שנים האלגוריתמים היציבים (כמו counting/radix) הם לא כללים ומסתמכים על עוד מידע נתון בניגוד לאלגורתמים השואתים (כמו quicksort ו bublesort) שמסתמכים רק על אופרטור השוואה בין 2 אלמנטים ברשימה. המידע הנוסף הזה הוא זה שמאפשר לרדת מחסם ה NlogN.כפי שרשום, היתרון של QuickSort הוא שאפשר לממש אותו ביעילות למעבדים. החיסרון שלו הוא שבפועל אפשר לייצר סידרת קלט שתגרום לו במקרה הגרוע לעבוד בסיבוכיות של N^2.מנגד, אלגוריתם מיון כמו HeapSort מבטיח תמיד למיין בחסם NlogN (אם כי בפועל הוא לרוב קצת יותר איטי מ QS).
פורסם 2007 בפברואר 2218 שנים אין מה להתווכח על זה... N Log N. זה זמן הריצה המינימלי (לאורך זמן) הדרוש למיין מערך בגודל N. זה פשוט לא נכוןO(nlog(n) זה החסם לזמן הריצה שדרוש למיון שמבוסס על השוואות במקרה הכללי.בהרבה מקרים יש לך מידע נוסף שמאפשר לך לעשות את המיון יותר מהר, למשל (כמו שנאמר קודם) radix sort, שפועל ב- O(n).יש מיונים שמניחים שסדר האיברים ההתחלתי מקיים תנאים מסוימים (למשל סדרת ז'ורדן) וגם הם מאפשרים חיפוש מהיר יותר, אפילו שמדובר בהשוואות.
פורסם 2007 בפברואר 2218 שנים לטעמי הכי פשוט הוא הbubble sort...אבל צריך לשים את הערכים(המספרים במערך)
פורסם 2007 בפברואר 2218 שנים BozoSort יותר פשוט. בודקים אם הרשימה מסודרת, אם לא בוחרים 2 מספרים רנדומלים ומחליפים את התוכן של האינדקסים ברשימה וחוזרים להתחלה. אם הרשימה מסודרת סיימנו (רק יכול להיות שזה אף פעם לא יסתיים).
פורסם 2007 בפברואר 2218 שנים נו ומה היעלות של האלגוריתם וגם כן לא הבנתי מתי הוא מסתיים בדיוק?בהחלט יכול להיות מצב שתיהיה לולאה אין סופית(אם משתמשים בלולאה)...
פורסם 2007 בפברואר 2218 שנים יותר קל לנתח את הסיבוכיות של אחיו הגדול, BogoSort, שפשוט בודק אם הרשימה מסודרת, אם לא הוא מערבב אותה (פרמוטציה שלה) ובודק שוב עד שזה מסודר. הסיבוכיות O(N*N!)(אבל זה תלוי במספר המופעים של הפרמוטציות השונות).ד"א אם משתמשים ביוצר מספרים רנדומלים אמיתי (לא כמו שיש במחשבים) אזי מובטח שכל האלגוריתמים האלו יסתיימו על פי משפט הקוף המקליד: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
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.