מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/אלגוריתמים למיון בזמן לינארי

מיון מבוסס השוואות (לדוגמה מיון הכנסה, מיון מיזוג, או Quicksort) הוא כללי מאד: האלגוריתם מניח מעט מאד על האיברים - כל שהוא מניח הוא שהוא יכול להשוות כל זוג איברים. המחיר לכלליות זו הוא חסם תחתון של $\displaystyle \Omega (n\cdot \log(n))$.

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

כדאי לדעת: בספר הקורס, הפרק "Sorting in Linear Time" עוסק בנושאים אלה.

מיון יציב

נתחיל בהגדרה נוספת על שיטות מיון - מיון יציב.

נניח שברצוננו למיין את המערך שבתרשים הבא - A. הדרישה היחידה שלנו היא שהתוצאה תהיה כבB. ‏

מיון יציב.

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

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

דוגמה: המערך בC ממוין עפ"י שם. אם ממיינים אותו במיון יציב עפ"י מספר שיעורי הבית, אז נקבל את המערך העליון בD. שני האיברים שעבורם #שיעורי בית = 2, ממוינים עדיין גם עפ"י שם.

מימוש C++ std::stable_sort

מיון ספירה

האלגוריתם

מיון ספירה ישים כשאנו יודעים שכל איברי המערך הם מספרים בתחום $\displaystyle [1,k]$, עבור $\displaystyle k$ כלשהו. הוא פועל ע"י ספירת כל האיברים הקטנים או שווים לערך כלשהו.

# Counting sort. 
# Takes an array (Values), and a number (k).
# Each one of (Values) is in the range 1...k.
# Returns an array of the same elements, sorted in increasing order.
Counting-Sort(Values, k)
1	Count = Make-Array(k)

2	for i in [1, ..., k]
3		Count[i] = 0
	
4	for j in [1, ..., Length(Values)]
5		value = Values[j]
6		++Count[value]
	
7	for i in [2, ..., k]
8		Count[i] = Count[i] + Count[i - 1]
	
9	Sorted = Make-Array(Length(Values))
	
10	for j in [Length(Values), ..., 1]
11		value = Values[j]
12		count = Count[value]
13		Sorted[count] = value
14		--Count[value]
	
15	return Sorted

נקבע את $\displaystyle n$ כLength(Values).

1-3 מייצרות מערך חדש, Count באורך $\displaystyle k$, ומאפסות אותו. 4-6 עוברות על Values ומעדכנות בCount את מספר הפעמים בהן ראו כל אחד מהאיברים. נשים לב שבשלב זה, Count[i] מכיל את מספר הפעמים בהם מופיע i בValues.‏ 7-8 מחברות כל איבר של Count לאיברים הקודמים לו. נשים לב שבשלב זה, Count[i] מכיל את מספר הפעמים בהם מופיע איבר קטן או שווה לi בValues.

דוגמה: נניח שValues == [2, 1, 1, 3].‏ בתרשים הבא, A מראה את Values,‏ B מראה את Count לפני 7,‏ ו C מראה את Count לפני 9. מיון ספירה.

9 מייצרת מערך חדש, Sorted,‏ 10-14 מעתיקות את איברי Values אליו (בסדר ממויין), ו$\displaystyle 15$ מחזירה אותו. כעת נתמקד ב10-14. הן פשוט עוברות בלולאה אחורה על איברי Values. כאשר נתקלים באיבר value, מעתיקים אותו לּSorted במקום Count[value], ומורידים את ערך Count[value] ב$\displaystyle 1$.

נכונות

משפט: Counting-Sort מחזיר את איברי Values ממוינים (כSorted ב15).

הוכחה: כפי שצויין מקודם, בדיוק לפני שורה 9, Count[i] מכיל את מספר הפעמים בהם מופיע איבר קטן או שווה לi בValues. מכאן קל לראות שהאיבר 1 אמור להופיע במקומות 1, ..., Count[1], האיבר 2 אמור להופיע במקומות Count[1] + 1, ..., Count[2], האיבר 3 אמור להופיע במקומות Count[2] + 1, ..., Count[3], וכולי. ואכן, 13-14 ידאגו, בהתקלן באיבר $\displaystyle i$, להציב אותו במקומות Count[i],‏ Count[i - 1],‏ Count[i - 2],‏ וכולי.

קל מאד להוכיח את המשפט הבא.

משפט: Counting-Sort הוא מיון יציב.‏

ניתוח סיבוכיות

נשים לב שמיון ספירה מורכב למעשה משתי לולאות באורך $\displaystyle n$ ושתי לולאות באורך $\displaystyle k$. מכאן נקבל את המשפט הבא.

משפט: Counting-Sort פועל בזמן $\displaystyle \Theta (n+k)$.‏‏

נשים לב שאם $\displaystyle k$ הוא קבוע, אז $\displaystyle \Theta (n+k)$ הוא פולינום ב$\displaystyle n$ מדרגה 1. מכאן נקבל את המשפט הבא.

משפט: אם $\displaystyle k$ הוא קבוע, אז Counting-Sort פועל בזמן $\displaystyle \Theta (n)$.‏‏

מיון Radix

האלגוריתם

מיון Radix פועל על איברים שכ"א מהם הוא מספר בן $\displaystyle d$ ספרות, וכל ספרה יכולה לקבל $\displaystyle k$ ערכים אפשריים.

דוגמה: נתן לחשוב על מספר תעודת זהות כמספר שעבורו $\displaystyle d=9$ ו$\displaystyle k=10$.

הרעיון הוא להשתמש $\displaystyle d$ פעמים במיון ספירה: ראשית ממיינים את המספרים לפי הספרה הפחות משמעותית, לאחר מכן ממיינים את המספרים לפי הספרה הבאה הפחות משמעותית, וכן הלאה.

דוגמה: להלן מיון Radix במקרה $\displaystyle d=3$, $\displaystyle k=10$: מיון Radix. A מציג את שלושת המספרים במצב הראשוני. ממיינים אותם (במיון Radix) עפ"י העמודה הימנית ביותר, ומקבלים את התוצאה בB. שוב ממיינים אותם (במיון Radix) עפ"י העמודה האמצעית, ומקבלים את התוצאה בC. ממיינים אותם פעם נוספת (במיון Radix) עפ"י העמודה השמאלית ביותר.

עכשיו תורכם: מדוע חשוב למיון Radix שמיון ספירה הוא מיון יציב?

נכונות

משפט: מיון Radix עובד.

הוכחה: ההוכחה היא באינדוקציה. נוכיח שלאחר האיטרציה ה$\displaystyle i$, המספרים ממויינים לפי $\displaystyle i$ הספרות המשמעותיות פחות.

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

(מעבר האינדוקציה) נניח שבתחילת האיטרציה ה$\displaystyle i$, המספרים ממויינים לפי $\displaystyle i-1$ הספרות המשמעותיות פחות, ונוכיח שבסוף האיטרציה ה$\displaystyle i$, המספרים ממויינים לפי $\displaystyle i$ הספרות המשמעותיות פחות. נקח שני מספרים $\displaystyle a$ ו$\displaystyle b$, ונחשוב היכן הם יישבו זה ביחס לזה בסוף האיטרציה ה$\displaystyle i$:

1. נניח שהספרה ה$\displaystyle i$ פחות משמעותית של שני המספרים שונה; בלי הגבלת הכלליות, נניח שזו של $\displaystyle a$ קטנה מזו של $\displaystyle b$. היות שהאיטרציה ה$\displaystyle i$ ממיינת לפי ספרה זו, אז בסוף האיטרציה, $\displaystyle a$ תשב לפני $\displaystyle b$.
2. נניח שהספר ה$\displaystyle i$ פחות משמעותית של שני המספרים זהה, אך $\displaystyle i-1$ הספרות המשמעותיות פחות אינן כולן זהות; בלי הגבלת הכלליות, נניח שאלו של $\displaystyle a$ קטנות מאלו של $\displaystyle b$. לפי הנחת האינדוקציה, בתחילת האיטרציה ה$\displaystyle i$,‏ $\displaystyle a$ יישבה לפני $\displaystyle b$. היות שהמיון יציב, נובע גם שבסוף האיטרציה, $\displaystyle a$ תשב לפני $\displaystyle b$.

ניתוח סיבוכיות

מיון Radix הוא למעשה הפעלה בת $\displaystyle d$ פעמים של מיון ספירה. מכאן נקבל את המשפט הבא.

משפט: מיון Radix פועל בסיבוכיות $\displaystyle \Theta (d\cdot (n+k))$.

נשים לב שאם $\displaystyle d$ ו$\displaystyle k$ קבועים, אז $\displaystyle \Theta (d\cdot (n+k))$ הוא פולינום ב$\displaystyle n$ מדרגה 1. מכאן נקבל את המשפט הבא.

משפט: עבור $\displaystyle d$ ו$\displaystyle k$ קבועים, מיון Radix פועל בסיבוכיות $\displaystyle \Theta (n)$.

הפרק הקודם: החסם התחתון על מיון מבוסס-השוואות

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

הפרק הבא: תכנון דינאמי