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

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

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

תבנית:הארה

מיון יציב

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

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

מיון יציב.

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

תבנית:מבנה תבנית

תבנית:מבנה תבנית

תבנית:מבנה תבנית

מיון ספירה

האלגוריתם

מיון ספירה ישים כשאנו יודעים שכל איברי המערך הם מספרים בתחום $[1,k]$, עבור $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

נקבע את $n$ כתבנית:קוד בשורה.

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

תבנית:מבנה תבנית

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

נכונות

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

תבנית:משפט

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

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

תבנית:משפט

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

מיון Radix

האלגוריתם

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

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

תבנית:משימה

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

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

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

תבנית:משפט

תבנית:מבני נתונים ואלגוריתמים - מחברת קורס