עיון בהיר במיון מהיר

מבין כל אלגוריתמי המיון המפורסמים, מיון מהיר הוא החביב עלי, בגלל שהוא כל כך מוזר. ראשית, זה אלגוריתם מיון שזמן הריצה שלו במקרה הגרוע שלו הוא \( \Theta\left(n^{2}\right) \), ובפועל הביצועים שלו גרועים במקרה הזה יותר מאשר אלו של מיון בחירה ומיון הכנסה, ולמרות זאת במקרה ה”ממוצע” (מה זה? נסביר בהמשך) הביצועים שלו דווקא מצויינים; שנית, המקרה הגרוע ביותר עבור המימוש הנאיבי שלו הוא זה שבו המערך כבר ממוין, וזה משעשע. לבסוף, הוא כל כך פשוט מבחינה רעיונית שאפשר לתאר אותו, בשפת התכנות המתאימה, בעזרת קוד פשוט ביותר:

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (x:xs) = (quicksort smaller) ++ [x] ++ (quicksort larger)
    where
        smaller = [a | a <- xs, a <= x]
        larger  = [b | b <- xs, b > x]

קטע הקוד הזה, בשפת Haskell, הוא דוגמה פופולרית בספרים/מאמרים על השפה (היפהפיה) הזו, שממחיש יפה את האופי ה”מתמטי” של ההגדרה של המיון. השורה הראשונה עשויה להיראות מפחיד למי שלא בקיאים בסינטקס של הסקל אבל היא בסך הכל אומרת ש-quicksort היא פונקציה שלוקחת רשימה של איברים מטיפוס a (כש-a הוא Ord - משהו שניתן להשוואה) ומחזירה רשימה של איברים מטיפוס a. כלומר, זו פשוט הגדרה מתמטית של פונקציה. השורה הבאה בסך הכל אומרת שעל רשימה ריקה, quicksort מחזיר רשימה ריקה. לאחר מכן מגיעה ההגדרה של מה ש-quicksort עושה בפועל: הוא מקבל קלט שעליו הוא חושב בתור איבר \( x \) (“איקס”) ועוד רשימה של איברים \( xs \) (“איקסים”). כלומר, אנחנו אוטומטית מפרקים את הרשימה שקיבלנו ל”איבר ראשון ועוד רשימה של כל יתר האיברים”. והפלט שאנחנו מחזירים הוא שרשור של שלוש רשימות: רשימה בשם smaller שאותה אנחנו ממיינים רקורסיבית עם quicksort; רשימה שהאיבר היחיד בה הוא \( x \), ורשימה בשם larger שגם אותה אנחנו ממיינים עם quicksort. ואיך מוגדרות הרשימות הללו? זה מה שכתוב אחרי ה-where: הרשימה smaller כוללת את כל האיברים של \( xs \) שקטנים או שווים ל-\( x \), ואילו larger כוללת את כל האיברים של \( xs \) שגדולים מ-\( x \).

זה הכל.

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

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

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

def quicksort(list, start = 0, finish = list.length - 1)
  return list if start >= finish
  middle = partition(list, start, finish)
  quicksort(list, start, middle-1)
  quicksort(list, middle + 1, finish)
  return list
end

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

אחרת, האלגוריתם קורא לפונקציה partition, שעושה שני דברים: היא בוחרת איבר ציר, ולאחר מכן גם מסדרת מחדש את list (רק באיזור שבין start ו-finish, כמובן) כך שכל האיברים ברשימה שקטנים מהציר יהיו משמאלו וכל מי שגדולים מהציר יהיו מימינו; לסיום היא מחזירה את האינדקס של איבר הציר ברשימה המסודרת. כעת כל שנותר לעשות הוא לקרוא למיון מהיר מחדש על שתי תתי-הרשימות של “מי שקטנים מהציר” ו”מי שגדולים מהציר”. שימו לב שהציר עצמו אינו נכלל באף אחת מהרשימות, כך שבהכרח שתיהן קטנות יותר מהרשימה המקורית ולכן אין סיכוי שנקלע ללולאה אינסופית.

צריך להשתכנע שהאלגוריתם באמת ממיין את הרשימות, אבל זה די ברור. אחרי שתי הקריאות הרקורסיביות למיון מהיר, אנחנו מקבלים ש-list מורכבת משלושה חלקים: כל מי שהיו קטנים מהציר, כשהם ממויינים; כל מי שגדולים מהציר, כשהם ממויינים; והציר באמצע בין שתי הרשימות הללו. אם הרשימה הכוללת לא הייתה ממויינת זה היה אומר שיש \( a,b \) כך ש-\( a>b \) אבל \( a \) דווקא נמצא משמאל ל-\( b \) ברשימה. לא ייתכן ש-\( a,b \) שונים מהציר ושניהם משמאל או מימין לו כי זה היה מראה שאחת משתי תת-הרשימות לא ממויינת; ולכן \( a \) בהכרח נמצא מימין לאיבר הציר (או שווה לו) ו-\( b \) נמצא משמאל לאיבר הציר (או שווה לו). זהו זה.

נשאר להבין איך מממשים את partition. קוד:

def partition(list, start, finish)
  pivot_index = choose_pivot(list, start, finish)
  pivot = list[pivot_index]
  list.swap(pivot_index, finish)
  a = start - 1
  for i in start...finish
      if list[i] < pivot
	a = a + 1
     	list.swap(a,i)
      end
  end
  list.swap(finish, a+1)
  return a+1
end

גם כאן הקוד עדיין לא שלם כי הוא תלוי במימוש של choose_pivot. בקוד ההסקל פשוט בחרנו את האיבר הראשון, אבל כאן אני מאפשר קצת יותר חופש בחירה (מסיבות שיובהרו בהמשך). אז קוראים ל-choose_pivot שמחזיר את האינדקס של איבר הציר, ואז pivot עצמו מקבל את הערך של איבר הציר, ואז אנחנו מעיפים את איבר הציר מהדרך - שמים אותו בסוף הרשימה. כעת אנחנו מתחזקים משתנה a שאומר “מה הקצה הימני של רשימת כל האיברים שקטנים מאיבר הציר”. בהתחלה זו רשימה ריקה, אז הקצה הימני הוא לפני תחילת הרשימה שאנחנו מטפלים בה (מיון מהיר מבלבל למדי מבחינת אינדקסים בקטע הזה, והתיאור המילולי שנתתי עוזר לזכור מה צריך לעשות, לדעתי).

מכאן ואילך הפעולה שלנו פשוטה: אנחנו עוברים סדרתית על כל האינדקסים של איברים בחלק הרלוונטי ברשימה (החל מ-start ועד ל-finish לא כולל). אם נתקלנו באיבר שקטן מאיבר הציר, אנחנו מקדמים את a ב-1 ואז מחליפים את מי שכרגע נמצא במקום a עם האיבר במקום i (שימו לב שבהחלט עשוי לקרות בהתחלה שאיבר יוחלף עם עצמו). בסופו של דבר, אחרי שסיימנו לעבור על הרשימה, אנחנו שמים את איבר הציר במקום a+1 ומחזירים את האינדקס שלו.

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

האם איבר שגדול מאיבר הציר עשוי גם כן להיות משמאלו כשנסיים? הדרך הפשוטה ביותר, לדעתי, לראות שזה לא יכול לקרות היא על ידי כך שנשים לב שערכו של a+1 בסיום, פחות הערך של start, שווה בדיוק למספר האיברים הקטנים מאיבר הציר ברשימה; זאת כי אנחנו מאתחלים את a להיות start-1 ומגדילים אותו ב-1 בכל פעם שמצאנו איבר שקטן מאיבר הציר. כעת, בסוף הריצה יש בדיוק a+1-start איברים משמאל לאיבר הציר, וכבר ראינו שכל מי שקטן מאיבר הציר אכן יהיה משמאלו, ולכן פשוט “אין מקום” לאיברים גדולים מאיבר הציר שם.

זה משלים את ההוכחה שמיון מהיר עובד. זה עדיין לא מטפל במה שהוא העיקר כאן - כמה מהר מיון מהיר עובד? התשובה המתבקשת “מהר, הרי הוא מיון מהיר” לא עובדת. למעשה, באופן מפתיע למדי, מיון מהיר במקרה הגרוע עובד לאט.

בואו נזכר איך טיפלנו במיון מיזוג: שם אמרנו שזמן הריצה מקיים את הנוסחה הרקורסיבית \( T\left(n\right)=2T\left(\frac{n}{2}\right)+O\left(n\right) \), כאשר ה-\( O\left(n\right) \) היה הזמן שנדרש למיזוג וה-\( T\left(\frac{n}{2}\right) \) היה הזמן שנדרש למיון שני תת-הרשימות. מתקבל על הדעת שלמיון מהיר תהיה נוסחה דומה, אבל יש כאן בעיה קטנה: בעוד מיון מיזוג מפצל את הרשימה תמיד לשני חלקים שווים בגודלם, מיון מהיר מפצל את הרשימה לשני תת-רשימות של “כל האיברים שגדולים יותר מאיבר הציר” ו”כל האיברים שקטנים יותר מאיבר הציר”. אין שום סיבה בעולם להניח ששתי הרשימות הללו יהיו מאותו אורך. יש רק מקרה אחד שבו הן מאותו אורך - אם איבר הציר הוא החציון של הרשימה (חציון של רשימה מוגדר כאיבר שגדול מחצי מהאיברים בה וקטן מחצי מהאיברים בה - לרשימה באורך זוגי יש שני חציונים). אלא שאצלנו לא בוחרים את איבר הציר להיות החציון בהכרח. בקוד ההסקל שלי בחרנו אותו להיות האיבר הראשון ברשימה. לפעמים בוחרים אותו בתור האיבר האחרון ברשימה. בכל מקרה עושים את זה בלי שיהיה לנו מושג מה הגודל שלו ביחס לשאר אברי הרשימה. התוצאות עשויות להיות הרסניות.

בואו נסתכל על המקרה ההרסני הבא: הרשימה ממוינת, ואנחנו בוחרים בתור איבר הציר תמיד את האיבר הראשון ברשימה (אותה בעיה תהיה גם אם נבחר אותו להיות האיבר האחרון ברשימה). במקרה הזה, נבזבז \( O\left(n\right) \) זמן על הרצת partition מיותרת, שבסופה נקבל שתי תת-רשימות: אחת שכוללת את כל האיברים שקטנים מאיבר הציר, אבל זו רשימה ריקה כי איבר הציר הוא האיבר הקטן ביותר ברשימה המקורית. תת-הרשימה השניה כוללת את כל אברי הרשימה פרט לאיבר הציר. כלומר, עכשיו נריץ רקורסיבית את מיון מהיר על רשימה מגודל 0 ועל רשימה מגודל \( n-1 \), וכך זה יימשך. קיבלנו את נוסחת הנסיגה \( T\left(n\right)=T\left(n-1\right)+\Theta\left(n\right) \) שלא קשה לראות שפתרונה הוא \( T\left(n\right)=\Theta\left(n^{2}\right) \). בבירור יש כאן בעיה שצריך לפתור איכשהו. פתרונות נאיביים כמו “בדוק אם המערך ממויין לפני שתתחיל” לא ממש יעזרו כי גם במערך שהוא “כמעט” ממוין עדיין תהיה לנו בעיה דומה ואי אפשר להותיר אותו לא ממויין.

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

דרך אחרת לפתור את הבעיה, שנשמעת מטופשת אבל אין לזלזל בה, היא לטעון שבכלל אין בעיה. שאמנם, זמן הריצה של האלגוריתם עבור המקרה הגרוע ביותר הוא \( \Theta\left(n^{2}\right) \), אבל עבור המקרה הממוצע זמן הריצה הוא מצוין. כאן נשאלת השאלה מהו המקרה ה”ממוצע”, וזה כמובן תלוי בשאלה מהו הקלט. אם, למשל, יש לנו רשימת שירים בנגנן מוזיקה שממויינת כרגע לפי אלבום ואנחנו עוברים למיין אותה לפי שם השיר, סביר להניח שתיראה “אקראית” ביחס לפרמטר הזה. לעומת זאת, ביחס לפרמטר “שם היוצר/להקה” הרשימה בוודאי לא תיראה אקראית (כי שירים ששייכים לאותו אלבום ישתייכו גם לאותה להקה, כנראה). בקיצור, זה עניין סבוך למדי להעריך מה סוג הקלטים שהולכים לטפל בו (עם זאת, בעולם האמיתי זה דבר שכדאי להתחשב בו כשבאים לבחור באיזה מיון להשתמש). אנחנו נבחר בגישה הפשוטה ונניח ש”המקרה הממוצע” הוא פשוט רשימה אקראית.

זה מעביר אותנו לפתרון השלישי, שבמובן מסוים מכליל את השני והוא מה שאני רוצה להשתמש בו: נהפוך את מיון מהיר לאלגוריתם הסתברותי:

def choose_pivot(list, start, finish)
  return start + rand(finish-start)
end

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

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

אפשר לבצע ניתוח הסתברותי שיאמר משהו בסגנון “בהסתברות \( \frac{2}{3} \) האלגוריתם ירוץ בסיבוכיות זמן \( O\left(n\log n\right) \)”, אבל אנחנו נעשה משהו חזק יותר - נדבר על תוחלת זמן הריצה של האלגוריתם. התוחלת היא ממוצע משוקלל; בהינתן קלט נתון כלשהו, אנחנו סוכמים את כל זמני הריצה האפשריים של האלגוריתם על הקלט, כאשר כל זמן ריצה מוכפל בהסתברות שהוא יתקבל. באופן הזה, אם האלגוריתם לפעמים מציג ביצועים שהם ממש איומים, אנחנו מתחשבים בכמה איומים הביצועים.

החסרון של מעבר לדיון הסתברותי הוא, כמובן, שצריך לדעת הסתברות כלשהי בשבילו. לא יותר מדי; אבל משהו תצטרכו לדעת. עבור מי שלא יחזיק מעמד עד הסוף רק נגלה את הסיום המפתיע: זמן הריצה של מיון מהיר ההסתברותי, בתוחלת, הוא \( \Theta\left(n\log n\right) \)!

שוק, מה?

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

ראשית, מה שנרצה לספור הוא את מספר ההשוואות שהאלגוריתם מבצע. מספר ההחלפות (הפעולה ה”בסיסית” האחרת) בכל הפעלה של partition חסום על ידי מספר ההשוואות ועוד 2, כך שזה לא באמת מגביל את כלליות הניתוח שלנו (אם מספר ההשוואות הוא \( \Theta\left(n\log n\right) \) כך יהיה גם מספר ההחלפות). לא קשה לראות שכל שאר העבודה שהאלגוריתם מבצע (פרט להחלפות/השוואות) היא \( O\left(n\right) \) כי partition ייקרא לכל היותר \( n \) פעמים, שהרי אחרי כל קריאה ל-partition אחד מהאיברים ברשימה (זה שנבחר בתור איבר הציר) יוצא מהמשחק.

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

תשובה לשאלה הזו מסיימת את הניתוח, כי מה שנשעשה הוא להגדיר משתנה מקרי שייקרא \( X_{ij} \) שמקבל 1 אם \( i,j \) הושוו ו-0 אם לא, ואז המשתנה המקרי שסופר את מספר ההשוואות הכולל שביצע האלגוריתם בריצה אקראית מסויימת שלו הוא \( X=\sum_{i<j}X_{ij} \), ולכן, מלינאריות התוחלת, תוחלת מספר ההשוואות שיבצע האלגוריתם היא \( \mbox{E}\left[X\right]=\mbox{E}\left[\sum_{i<j}X_{ij}\right]=\sum_{i<j}\mbox{E}\left[X_{ij}\right]=\sum_{i<j}\mbox{Pr}\left[X_{ij}=1\right] \). אם כל זה נשמע לכם כמו ג’יבריש - יש לי פוסט על העניינים הללו אבל עדיף ללמוד אותם בצורה מסודרת.

אבל רגע, מה זה בכלל \( i,j \)? אני מניח שחשבתם באופן מובלע שאלו האינדקסים של האיברים ברשימה, ובהחלט אפשר לנקוט בשיטת הסימון הזו; אבל עוד מעט נראה שהרבה יותר אפקטיבי למספר את האיברים על פי גודלם. כלומר, איבר מס’ \( i \) יהיה האיבר מספר \( i \) בגודלו ברשימה. אם הרשימה היא \( \left[3,1,5,4,2\right] \) אז עבור \( i=2 \) נקבל את האיבר \( 2 \) ועבור \( i=3 \) נקבל את האיבר \( 3 \), למרות שהאינדקסים שלהם ברשימה הם שונים. יש כאן הגיון לא מועט כי בכל מקרה הסדר המקורי בתוך הרשימה עשוי להיעלם לגמרי אחרי בחירת איבר הציר הראשון וסידור אברי הרשימה על פיו; מה שמעניין הוא הסדר האמיתי של האיברים, כי שני איברים שבאים אחד אחרי השני בסדר הרבה יותר קשה להפריד על ידי איבר ציר מאשר שני איברים “רחוקים”.

ההסתברות שנשווה את \( i,j \) היא ההסתברות שיקרה הדבר הבא: או ש-\( i \) ייבחר כאיבר ציר, או ש-\( j \) ייבחר כאיבר ציר, וזה בזמן שבו \( i,j \) עדיין נמצאים באותה תת-רשימה. כלומר, לפני שנבחר איבר ציר כלשהו ביניהם. לצורך כך, הבה ונחשוב על הקטע של כל האיברים שבין \( i \) ו-\( j \), כולל שניהם; אסמנו \( \left[i,j\right] \). הקטע הזה מוכל בשלמותו בכל תת-רשימה שעשויה לצוץ במהלך האלגוריתם, וזאת עד הפעם הראשונה שבה נבחר איבר ציר מתוך \( \left[i,j\right] \). בנוסף, הפעם הראשונה הזו תבוא בהכרח, אחרת האלגוריתם לא היה מסתיים. מכאן שהשאלה היא רק - איזה איבר מתוך \( \left[i,j\right] \) ייבחר לראשונה?

התשובה היא שלכל האיברים ב-\( \left[i,j\right] \) יש אותו סיכוי להיבחר, בכל פעם שיש בחירה שכזו, וזאת תחת ההנחה שאיבר הציר אכן נבחר באופן אחיד בכל איטרציה. אם לכל האיברים ב-\( \left[i,j\right] \) יש אותו סיכוי להיבחר בכל פעם שבה מתבצעת בחירה, אז לכל אחד מהם יש אותו סיכוי להיבחר ראשון. כמה איברים יש בסך הכל ב-\( \left[i,j\right] \)? ובכן, \( j-i+1 \) (תמיד קשה לזכור האם צריך לעשות פלוס 1 או לא; אני תמיד פשוט מציב \( i=1,j=3 \) ובודק מה המספר יוצא כדי להיזכר). כלומר, לכל איבר ב-\( \left[i,j\right] \) יש סיכוי של \( \frac{1}{j-i+1} \) להיות הראשון שנבחר מתוך \( \left[i,j\right] \). אנחנו רוצים לדעת מה הסיכוי שהאיבר הראשון הזה יהיה \( i \) או שיהיה \( j \), ולכן ההסתברות היא \( \mbox{Pr}\left[X_{ij}=1\right]=\frac{2}{j-i+1} \).

עכשיו יתר הניתוח הופך לפשוט. תוחלת מספר ההשוואות של האלגוריתם היא \( \sum_{i<j}\frac{2}{j-i+1} \) ולכן כל מה שנותר לנו לעשות הוא חישוב סכום. כדי לפשט את החישוב נוח לפצל את הסכום הזה לשני סכומים, אחד על \( i \) והשני על \( j \):

\( \sum_{i<j}\frac{2}{j-i+1}=2\sum_{i=1}^{n}\sum_{j=i+1}^{n}\frac{1}{j-i+1}=2\sum_{i=1}^{n}\sum_{k=1}^{n-i}\frac{1}{k+1} \)

המעבר האחרון הוא החלפת משתנה רגילה: \( k=j-i \). עכשיו, חישוב מדויק של ערכו של הטור שקיבלנו הוא לא פשוט, ולכן נשתמש בחסמים עליונים:

\( 2\sum_{i=1}^{n}\sum_{k=1}^{n-i}\frac{1}{k+1}\le2\sum_{i=1}^{n}\sum_{k=1}^{n}\frac{1}{k}\le2n\cdot H_{n} \)

כאשר \( H_{n}=\sum_{k=1}^{n}\frac{1}{k} \) הוא מה שנקרא מספר הרמוני, כי הוא סכום חלק של הטור ההרמוני \( \sum_{k=1}^{\infty}\frac{1}{k} \) שכבר הוזכר בבלוג.

אפשר לסיים כאן על ידי זה שנציין ש-\( H_{n}\le\lg n+1 \), אבל ייתכן שזה לא מספיק לכם ואתם רוצים גם לראות איך מוכיחים את זה. מצוין! זה עוד תעלול קטן ונחמד שכדאי להכיר. הרעיון הוא לחלק את הסכום \( \sum_{k=1}^{n}\frac{1}{k} \) להרבה תת-סכומים קטנים שכל אחד מהם אפשר לחסום מלמעלה בצורה פשוטה כך שהתוצאה הסופית היא עדיין קטנה יחסית. החסם הנאיבי ביותר הוא זה שבו חוסמים את כל הסכום על ידי האיבר הראשון בו (שהוא האיבר הגדול ביותר), מה שנותן לנו את הסכום \( \sum_{k=1}^{n}1=n \) שהוא בוודאי גדול מדי, ולכן צריך לבצע את החלוקה לתת-סכומים.

בדרך כלל מחלקים את הסכום לתתי-סכומים שווים בגודלם (למשל, חוצים אותו באמצע), אבל כאן משתלם הרבה יותר לבצע חלוקה שונה: \( 1|2,3|4,5,6,7|8,9,10,11,12,13,14,15,\dots \) כשהקווים מייצגים סוף של תת-סכום אחד והתחלה של תת-סכום אחר. פורמלית, כל תת-סכום כולל את כל האיברים \( \frac{1}{k} \) כאשר \( k \) הוא איבר בתחום שבין \( 2^{i} \) ועד \( 2^{i+1}-1 \). כמה סכומים כאלו יש? ובכן, עד אשר \( 2^{i}>n \), כלומר \( i>\lg n \). לכן נקבל:

\( \sum_{k=1}^{n}\frac{1}{k}\le\sum_{i=1}^{\left\lceil \lg n\right\rceil }\sum_{k=2^{i}}^{2^{i+1}-1}\frac{1}{k} \)

אם נראה שהסכום הפנימי, \( \sum_{k=2^{i}}^{2^{i+1}-1}\frac{1}{k} \), הוא תמיד קטן מ-1, הרי שסיימנו; זה יוכיח שהסכום כולו קטן או שווה ל-\( \left\lceil \lg n\right\rceil \le\lg n+1 \). אבל איך נראה את זה? ובכן, כמה איברים יש בסכום הפנימי?

\( \left(2^{i+1}-1\right)-2^{i}+1=2^{i+1}-2^{i}=2^{i}\left(2-1\right)=2^{i} \)

ומה האיבר הגדול ביותר בסכום הפנימי? \( \frac{1}{2^{i}} \). ולכן, מה החסם העליון המיידי על הסכום הפנימי? \( \frac{2^{i}}{2^{i}}=1 \), וסיימנו.

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