מבני נתונים ומבוא לאלגוריתמים

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

מבוא למיון: הגדרה ומאפיינים

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

אלגוריתם מיון: אלגוריתם שמטרתו לסדר רשימה של איברים בסדר מסוים (לרוב מספרי או אלפביתי).

יציבות (Stability): אלגוריתם מיון יציב אם הוא שומר על הסדר היחסי של איברים בעלי מפתחות זהים. לדוגמה, אם במערך המקורי יש שני איברים 'A' ו-'B' עם אותו מפתח, ו-'A' מופיע לפני 'B', אז במיון יציב 'A' עדיין יופיע לפני 'B'.

מיון במקום (In-place Sort): אלגוריתם מיון הנחשב "במקום" אם הוא דורש כמות קבועה או לוגריתמית של זיכרון עזר (למעט הזיכרון הנדרש לאחסון הקלט עצמו).

אלגוריתמי מיון מבוססי השוואות

רוב אלגוריתמי המיון הנפוצים פועלים על ידי השוואת זוגות איברים. יעילותם נמדדת לרוב במונחי מספר ההשוואות ומספר ההחלפות.

מיון הכנסה (Insertion Sort)

אלגוריתם פשוט ויעיל עבור קלטים קטנים או כמעט ממוינים. הוא בונה את המערך הממוין איבר אחר איבר, על ידי הכנסת כל איבר למקומו הנכון בחלק הממוין של המערך.

סיבוכיות זמן: מקרה הטוב O(n) (כאשר המערך כבר ממוין), מקרה ממוצע וגרוע O(n²).
סיבוכיות מקום: O(1) (במקום).
יציבות: יציב.

מיון מיזוג (Merge Sort)

אלגוריתם מבוסס "הפרד ומשול". הוא מחלק את המערך לשני חצאים, ממיין כל חצי באופן רקורסיבי, ואז ממזג את שני החצאים הממוינים למערך אחד ממוין.

סיבוכיות זמן: O(n log n) בכל המקרים (טוב, ממוצע, גרוע).
סיבוכיות מקום: O(n) (לא במקום, דורש מערך עזר).
יציבות: יציב.

מיון ערימה (Heap Sort)

אלגוריתם המשתמש במבנה נתונים ערימה (Heap). הוא בונה ערימת מקסימום מהמערך, ואז מוציא את האיבר הגדול ביותר (שורש הערימה) n פעמים, וממקם אותו בסוף המערך.

סיבוכיות זמן: O(n log n) בכל המקרים.
סיבוכיות מקום: O(1) (במקום).
יציבות: לא יציב.

מיון מהיר (Quick Sort)

גם הוא אלגוריתם "הפרד ומשול". הוא בוחר איבר ציר (pivot), מחלק את המערך לשני חלקים: איברים קטנים מהציר ואיברים גדולים מהציר, ואז ממיין את שני החלקים באופן רקורסיבי.

סיבוכיות זמן: מקרה ממוצע O(n log n). מקרה גרוע O(n²) (כאשר בחירת הציר גרועה, למשל תמיד האיבר הקטן/גדול ביותר).
סיבוכיות מקום: O(log n) במקרה ממוצע (עבור עומק הרקורסיה), O(n) במקרה גרוע.
יציבות: לא יציב.

מיון מיזוג (Merge Sort)

תמיד O(n log n), יציב, אך דורש זיכרון עזר O(n). מתאים למיון רשימות מקושרות או נתונים שאינם נכנסים לזיכרון.

מיון מהיר (Quick Sort)

בממוצע O(n log n), במקום (O(log n זיכרון רקורסיה), אך לא יציב ועלול להיות O(n²) במקרה הגרוע. נחשב מהיר מאוד בפועל.

אלגוריתמי מיון שאינם מבוססי השוואות

אלגוריתמים אלו יכולים להשיג סיבוכיות זמן טובה יותר מ-O(n log n) בתנאים מסוימים, מכיוון שהם אינם כפופים לחסם התחתון של מיון מבוסס השוואות.

מיון ספירה (Counting Sort)

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

סיבוכיות זמן: O(n + k).
סיבוכיות מקום: O(n + k).
יציבות: יציב.
מגבלה: דורש שמפתחות המיון יהיו מספרים שלמים בטווח מוגבל.

מיון בסיס (Radix Sort)

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

סיבוכיות זמן: O(d(n + k)), כאשר d הוא מספר הספרות המקסימלי ו-k הוא בסיס המספרים (לרוב 10 או 256).
סיבוכיות מקום: O(n + k).
יציבות: יציב (בתנאי שאלגוריתם העזר יציב).
מגבלה: דורש שמפתחות המיון יהיו מספרים שלמים.

מיון מבוסס השוואות

פועל על ידי השוואת זוגות איברים. חסם תחתון של O(n log n). גמיש לסוגי נתונים שונים (כל עוד ניתן להשוות). דוגמאות: Merge Sort, Quick Sort, Heap Sort.

מיון שאינו מבוסס השוואות

לא משווה איברים ישירות. יכול להיות מהיר יותר מ-O(n log n) בתנאים מסוימים (לרוב מפתחות שלמים בטווח מוגבל). דוגמאות: Counting Sort, Radix Sort.

החסם התחתון למיון מבוסס השוואות

החסם התחתון למיון מבוסס השוואות: נושא זה הוא קריטי לבחינה, שכן הוא מספק הבנה תיאורטית עמוקה מדוע אלגוריתמים כמו Merge Sort ו-Heap Sort נחשבים אופטימליים. שאלות בבחינה עשויות לדרוש הוכחה או הסבר של החסם התחתון באמצעות עץ החלטות, או השוואה של אלגוריתמים שונים לאור חסם זה. הבנה זו מאפשרת להבחין בין מגבלות תיאורטיות של בעיה לבין יעילות של אלגוריתם ספציפי.

ניתן להוכיח כי כל אלגוריתם מיון מבוסס השוואות דורש לפחות O(n log n) השוואות במקרה הגרוע. הוכחה זו מתבצעת באמצעות מודל "עץ החלטות".

עץ החלטות

עץ החלטות מייצג את כל רצפי ההשוואות האפשריים שאלגוריתם מיון יכול לבצע. כל צומת פנימי בעץ מייצג השוואה בין שני איברים, וכל עלה מייצג סידור אפשרי אחד של המערך הממוין. מכיוון שיש n! תמורות אפשריות למערך בגודל n, חייבים להיות לפחות n! עלים בעץ ההחלטות. עומק העץ (מספר ההשוואות במקרה הגרוע) הוא לפחות log(n!). באמצעות קירוב סטירלינג, log(n!) הוא מסדר גודל של n log n.

שאלות לדיון

הסבירו מדוע מיון ספירה ומיון בסיס יכולים להיות מהירים יותר מ-O(n log n), ומתי לא ניתן להשתמש בהם.
השוו בין מיון מיזוג למיון מהיר במונחים של סיבוכיות זמן (מקרה גרוע וממוצע), סיבוכיות מקום ויציבות. מתי תעדיפו כל אחד מהם?
הדגימו כיצד מיון ערימה אינו יציב. תנו דוגמה למערך קלט שבו הסדר היחסי של איברים זהים אינו נשמר.
הסבירו את הרעיון של החסם התחתון למיון מבוסס השוואות באמצעות עץ החלטות.

נקודות לתשובת מודל

מיון שאינו מבוסס השוואות: מצריך מפתחות שלמים בטווח מוגבל (k). סיבוכיות O(n+k) או O(d(n+k)). אינו כפוף לחסם התחתון כי אינו מבצע השוואות ישירות, אלא משתמש בתכונות של המפתחות (למשל, ספירה או פירוק לספרות).
השוואת מיון מיזוג ומהיר:
- מיזוג: תמיד O(n log n), יציב, O(n) מקום. מתאים לנתונים גדולים או כאשר יציבות חשובה.
- מהיר: ממוצע O(n log n), גרוע O(n²), לא יציב, O(log n) מקום בממוצע. מהיר בפועל, טוב כאשר זיכרון עזר מוגבל ויציבות אינה קריטית.
אי-יציבות של מיון ערימה: דוגמה: [ (1, 'a'), (5, 'b'), (1, 'c') ]. לאחר בניית ערימה והוצאת איברים, ייתכן ש-(1, 'c') יופיע לפני (1, 'a'), למרות שבמקור היה אחריו. ההחלפות בערימה אינן שומרות על סדר יחסי.
חסם תחתון: עץ החלטות חייב להכיל לפחות n! עלים (מספר התמורות האפשריות). עומק עץ בינארי עם L עלים הוא לפחות log L. לכן, עומק העץ הוא לפחות log(n!) ≈ n log n. כל נתיב מהשורש לעלה מייצג רצף השוואות, והארוך ביותר הוא המקרה הגרוע.

מצאתם טעות או שחסר משהו?