נראה לכם שיש קשר בין ריקוד לארבעה אלגוריתמים למיון מערכים?
כמה חבר'ה מאוניברסיטה בטיזינבי חושבים שיש, והכי חשוב זה המוזיקה.
כולנו יודעים שכמעט בכל שפה אפשר למיין מערך עם פונקציית מיון כזו או אחרת. בטבע קיימים כמה אלגוריתמים למיון מערכים ואוניברסיטת Sapientia מטרנסילבניה החליטה להציג אותם באופן מעניין.
מיון בועות (Bubble Sort)
אלגוריתם מיון שמשווה כל זוג אלמנטים סמוכים ומחליף ביניהם עד שהגדולים ביותר מגיעים לסוף.
מיון הכנסה (Insertion Sort)
האלגוריתם לוקח כל אלמנט ומשווה אותו לכל האלמנטים שלפניו כדי להכניס אותו במקום המתאים ברצף לפי הגודל. מיון הכנסה יעיל במיון מערכים קטנים.
Shell Sort
Shell Sort מנסה למיין את המערך "בערך" ולאחר מכן להשתמש במיון הכנסה כדי לסדר את הערכים באופן נכון, כיוון שמיון הכנסה עובד מהר על מערכים בערך ממוינים.
מיון בחירה (Selection Sort)
במיון בחירה, אלגוריתם איטי ולא יעיל, עוברים על כל האלמנטים, מוצאים את האלמנט הקטן ביותר, שמים אותו במקום הראשון וחוזרים על התהליך - מוצאים את האלמנט הקטן ביותר במערך (פרט לזה שנמצא במקום הראשון) ושמים אותו במקום השני.
מיון מהיר (Quick Sort)
ברוב שפות התכנות פונקציית המיון המובנית מבצעת את אלגוריתם המיון המהיר (Quick Sort).
האלגוריתם הזה יעיל במיון מערכים גדולים. הוא פועל בשיטת הפרד ומשול. בקצרה, זה אומר חילוק המערך לחלקים, אחד של מספרים הגדולים יותר מערך מסוים שנבחר, והשני של מספרים הקטנים יותר מאותו הערך. האלגוריתם הוא רקורסיבי.
כתבו בתגובות: איזה מיון הכי אהבתם?
בונוסים
עכשיו אפשר לא רק לראות אלא גם לשמוע את הסוגים השונים של המיונים.
בונוס נוסף: סרטון שמדגים מיון בועות ומיון מהיר באמצעות שני רובוטים חמודים שגם מתחרים ביניהם אחרי זה על הפרס הגדול - הרבה אלקטרונים כחולים. ממליץ לראות:
(תודה על הסרטון ל zuto.co.il.)
תגובות לכתבה:
לפי אורך הסרטון מבינים מה עובד יותר מהר :)
למרות שעם סידור התחלטי שונה התוצאות גם יהיו שונות.
השוואת מהירויות נאה ניתן לראות כאן http://www.sorting-algorithms.com
איזה משועממים הם
יפה
יש לזה הרבה משמעות ואפילו קורס שלם בתואר למדעי המחשב בשנה הראשונה- כאשר רוצים לדעת מה המהיר מביניהם- יש מושג שנקרא סיבוכיות. כל ריצה על מערך נקראת סיבוכיות O n כשה n מגדיר פעמי ריצות במערך. ונגיד ניתן לראות באלגוריתם כשכותבים אותו (באבל סורט לדוגמא שיש ריצה פעמיים על המערך. ולכן הסיבוכיות O n בריבוע! ככל שה n גבוה יותר הסיבוכיות גבוה יותר ופחות מהירה ופחות יעילה.
ניתן שוב לראות למשל במיון quick sort- סיבוכיות של O log 2 n כשה 2 הוא בסיס 2 וה n זה החזקה. כלומר האלגוריתם קוויק סורט מפצל ברקורסיביות (לרוב) את הריצה של המערך לבסיסים של 2 . (בינארי) ולכן אם נמדוד הרצה נראה שבאמת הריצה פה הרבה יותר נמוכה מה O N בריבוע.
תוספת חדשה לקולקציית הסרטונים.
מעכשיו אפשר לשמוע - איך נשמעים אלגוריטמי מיון שונים.
http://youtu.be/t8g-iYGHpEA
ממליץ להוסיף גם את הסרטון הנחמד הזה:
http://www.youtube.com/watch?v=o2dm4X-t8L0
הרובוטים האלה, אדיר :) הוספתי. תודה
אני רואה עכשיו ש-Quick Sort לא מופיע כאן בפני עצמו. אז הנה ריקוד העם ההונגרי שלו: https://www.youtube.com/watch?v=ywWBy6J5gz8
אתה יכול לערוך ולהוסיף?
כמובן. רק רציתי ליידע, כי זה מה שכתבת לעשות. :-)
מעולה. תודה :)