מערך כמעט ממויין

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

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

אני אתחיל מהתשובה הכי נאיבית שיכולה להיות – כדי למיין את הסדרה, אני יכולה להשתמש במיון מוכר ויעיל, למשל merge_sort שימיין את הסדרה ב-nlogn.

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

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

הרעיון הבא שעולה לי הוא למיין בעזרת “sliding window” –

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

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

וכן הלאה, עד שאמיין את האיברים n-1000 עד 1000, וכל הסדרה תהיה ממוינת.

אני אכתוב אלגוריתם ממש פשטני –

def sort_approximate(A,k):
	for i in range(0,len(A)-k):
		sorted_block = merge_sort(A[i:i+k])
		A[i:i+k] = sorted_block

אני אריץ דוגמא קטנה רק כדי לבדוק את נכונות האלגוריתם.
אני אשתמש ב-n=7 וב-k=3 (כאשר n הוא אורך הסדרה ו-k הוא המרחק של כל איבר מהמקום הממוין שלו).

A = 3, 1, 4, 2, 7, 6, 5

A(i=0) = 1, 3, 4, 2, 7, 6, 5
A(i=1) = 1, 2, 3, 4, 7, 6, 5
A(i=2) = 1, 2, 3, 4, 7, 6, 5
A(i=3) = 1, 2, 3, 4, 6, 7, 5
A(i=4) = 1, 2, 3, 4, 5, 6, 7

הדוגמא יצאה נכונה. לא רע בכלל.

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

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

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

def sort_approximate(A,k):
   sorted_A = list()
   for i in range(0,len(A)-k):
      block_min = min(A[i:i+k])
      sorted_A.append(block_min)
   return sorted_A

בפתרון הזה במקום למיין את כל הבלוק ב-klogk אני רק מחפשת את המינימום ב-(O(k,.

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

אני אריץ את הדוגמא שוב כדי לוודא שהפתרון נכון.

A = 3, 1, 4, 2, 7, 6, 5

sorted_A = []
sorted_A.append(min(3,1,4)) →  [1]
sorted_A.append(min(1,4, 2)) →  [1, 2]
sorted_A.append(min(4, 2, 7)) →  [1, 2, 2]
.
.
.

אוי, מצאתי באג. זו הסיבה שזה תמיד רעיון טוב להריץ דוגמא!

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

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

איזה מבנה נתונים יכול תמיד לעזור לי למצוא את המינימום? ערימה, כמובן.

אם אני אשתמש בערימת מינימום, ובכל פעם אכניס איבר נוסף לערימה, האיבר המינימלי יגיע לשורש ואני אוכל להשתמש בו.

מה תהיה הסיבוכיות של הפתרון הזה? הסיבוכיות של הכנסת איבר לערימה היא (O(logk והסיבוכיות של הוצאת איבר מהערימה היא (O(1. אז הסיבוכיות של האלגוריתם כולו תהיה (O(nlogk.

אשנה את האלגוריתם בהתאם.

def sort_approximate(A,k):
   sorted_A = list()
   heap = minHeap()

   for i in range(0,len(A)):
      heap.push(A[i])
      sorted_A.append(heap.top())
      heap.remove_top()
   return sorted_A

אני אריץ את הדוגמא שוב כדי לוודא שהפתרון נכון.

A = 3, 1, 4, 2, 7, 6, 5

sorted_A = []
heap = []
heap = [3]
sorted_A = [3]

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

def sort_approximate(A, k):
    sorted_A = list()
    heap = minHeap()

    for i in range(0, k):
        heap.push(A[i])

    for i in range(k, len(A)):
        heap.push(A[i])
        sorted_A.append(heap.top())
        heap.remove_top()
    return sorted_A

אני אריץ את הדוגמא שוב כדי לוודא שהפתרון נכון.

A = 3, 1, 4, 2, 7, 6, 5

sorted_A = []
heap = []
i=0
heap = [3]
i=1
heap = [1, 3]
i=2
heap = [1, 3, 4]
i=3
heap = [1, 2, 3, 4]
i=4
sorted_A = [1]
heap = [2, 3, 4]
heap = [2, 3, 4, 7]
i=5
sorted_A = [1, 2]
heap = [3, 4, 7]
heap = [3, 4, 7, 6]
i=6
sorted_A = [1, 2, 3]
heap = [4, 7, 6]
heap = [4, 5, 7, 6]

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

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

def sort_approximate(A, k):
    sorted_A = list()
    heap = minHeap()

    for i in range(0, k):
        heap.push(A[i])

    for i in range(k, len(A)):
        sorted_A.append(heap.top())
        heap.remove_top()
        heap.push(A[i])
    for i in range(0, k):
        sorted_A.append(heap.top())
        heap.remove_top()
    return sorted_A

אני אריץ דוגמא חלקית כדי לוודא שהתיקון עבד –

A = 3, 1, 4, 2, 7, 6, 5

sorted_A = []
heap = []
i=0
.
.
.
i=2
heap=[1,3,4]
i=3
sorted_A = [1]
heap=[3,4]
heap=[2,3,4]
.
.
.
i=5
sorted_A = [1, 2,3]
.
heap=[4,6,7]
i=6
sorted_A = [1, 2,3,4]
.
heap=[5, 6,7]
sorted_A = [1, 2,3,4,5]
sorted_A = [1, 2,3,4,5,6]
sorted_A = [1, 2,3,4,5,6,7]
return [1, 2,3,4,5,6,7]

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

למשל, עבור k=0.

A=[1,2]
sorted_A = []
heap = []
i=0
sorted_A.append(heap.top()) → Failure

במקרה שבו k=0 הערימה תהיה ריקה, ולא אוכל להוציא ממנה איברים. אבל מעבר לזה, במקרה בו k=0 המערך כבר ממויין (כל איבר נמצא במקומו הממויין) ולכן אפשר להחזיר אותו מייד.

def sort_approximate(A, k):
    if k == 0:
        return A
    sorted_A = list()
    heap = minHeap()

    for i in range(0, k):
        heap.push(A[i])

    for i in range(k, len(A)):
        sorted_A.append(heap.top())
        heap.remove_top()
        heap.push(A[i])
    for i in range(0, k):
        sorted_A.append(heap.top())
        heap.remove_top()
    return sorted_A

מה לגבי מקרה של מערך ריק? כיוון שהנחנו ש- k<=n אז יתקיים k=0 ונחזיר מערך ריק.

מה לגבי מקרה שבו k=n?

במקרה כזה הלולאה האמצעית לא תתקיים. הלולאה הראשונה תכניס k איברים לערימה, והלולאה השלישית תוציא אותם אחד אחד.

נראה שבזאת כיסיתי את כל מקרי הקיצון. הוריי!

אני יכולה לכתוב את האלגוריתם בקוד (כולל מימוש של ערימה אם יבקשו ממני, כמובן).

הקוד הגמור נמצא בגיט – https://github.com/mgershovitz/maya_solves/blob/master/approximate_sort.py