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

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

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

תבנית:הארה

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

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

תבנית:הארה

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

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

בשאר הדף נוכיח את המשפט הבא.

ההוכחה הנה קומבינטורית, ואינה קצרה במיוחד. שאר הדף עוסק בהוכחה.

בעיה קומבינטורית בקבצים

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

בעיה קומבינטורית בפרמוטציות

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

המשפט הבא טריביאלי.

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

מיון מבוסס-השוואות ופרמוטציות

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

כדוגמה למיון מבוסס-השוואות, נשתמש במיון הכנסה.

תהליך הכתיבה

תחילה מייצרים מערך בו כל איבר הוא זוג: הזוג ה$i$ מורכב מהאיבר ה$i$ בקבוצה, ומהמיקום $j$ של איבר מקורי זה בפרמוטציה.

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

Compare-And-Print(x, y)
1	if x > y
2		Print 1
3		return True

4	Print 0
5	return False


Insertion-Sort-Zip(Values)
1	for i in [1, ..., Length(Values)]
2		v = Values[i]

		# Insert Values[j] into the correct position of Values[1, ..., j].
3		j = i
4		while j > 1 and Compare-And-Print(Values[j - 1], v)
5			Values[j] = Values[j - 1]
6			--j

7		Values[j] = v

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

תבנית:שימו לב

תהליך הקריאה

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

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

Read-And-Compare(x, y)
1	if Read() == 1
2		return True

3	return False



Insertion-Sort-Unzip(Values)
1	for i in [1, ..., Length(Values)]
2		v = Values[i]

		# Insert Values[j] into the correct position of Values[1, ..., j].
3		j = i
4		while j > 1 and Read-And-Compare(Values[j - 1], v)
5			Values[j] = Values[j - 1]
6			--j

7		Values[j] = v

מעצם הצורה שבה בנינו את שני האלגוריתמים, קל לראות את המשפט הבא: תבנית:משפט

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

הוכחת החסם התחתון

כעת נוכל להוכיח את החסם התחתון על זמן הריצה של מיון מבוסס-השוואות. תבנית:הוכחה