א.16 — חיפוש, מיון ויעילות

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

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

מחברות האוניברסיטה הפתוחה — 10-אלגורתמים

חיפוש לינארי

הדרך הפשוטה ביותר לחפש ערך ברשימה היא חיפוש לינארי — Linear Search: עוברים על האיברים לפי הסדר עד שמוצאים את הערך. הפונקציה הבאה מחזירה את האינדקס הראשון שלו, או -1 אם אינו מופיע:

def find(numbers, value):
    for i in range(len(numbers)):
        if numbers[i] == value:
            return i
    return -1

print(find([3, 6, 1, 9, 10, 4], 10))

פלט

4

הערך 10 נמצא במקום החמישי, ולכן מוחזר האינדקס 4. ברשימה באורך n, במקרה הגרוע, כשהערך נמצא בסוף או אינו קיים כלל, נבדוק n איברים. כדי להשוות בין אלגוריתמים נהוג לתאר לא את מספר הפעולות המדויק אלא את קצב הגידול שלו ביחס לגודל הקלט. מסמנים קצב גידול כזה ב־O(n) (קוראים: "סדר גודל של n"): אם הרשימה גדלה פי עשרה, גם העבודה גדלה בערך פי עשרה. הסימון מתאר כיצד העבודה גדלה, לא זמן בשניות, ולכן הוא אינו תלוי במהירות המחשב.

חיפוש בינארי

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

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

def binary_find(numbers, value):
    left = 0
    right = len(numbers) - 1
    while left <= right:
        middle = (left + right) // 2
        if numbers[middle] == value:
            return middle
        if numbers[middle] < value:
            left = middle + 1
        else:
            right = middle - 1
    return -1

numbers = [3, 5, 7, 9, 12, 34, 55, 89]
print(binary_find(numbers, 55))
print(binary_find(numbers, 8))

פלט

6
-1

בחיפוש אחר 55 נבדקו רק שלושה איברים, 9, 34 ו־55, במקום שבעה בחיפוש לינארי. הגבול הימני הוא האינדקס האחרון, len(numbers) - 1. הלולאה נמשכת כל עוד נותר אזור לחיפוש; כשהערך אינו קיים, כמו 8 בדוגמה, הגבולות מצטלבים ומוחזר -1. מכיוון שכל צעד מחצה את הטווח, מספר הצעדים גדל כמו O(log n): הכפלת אורך הרשימה מוסיפה רק צעד אחד. זה הבדל עצום לעומת חיפוש לינארי ברשימות גדולות. עם זאת, מיון חדש של הרשימה לפני כל חיפוש הוא עבודה נוספת; החיסכון מתאים במיוחד לנתונים שכבר ממוינים או לחיפושים חוזרים באותה רשימה.

מיון — מה קורה בתוך sorted?

ראינו שחיפוש יעיל נשען על רשימה ממוינת, ולכן נעבור למיון. בפרק א.13 השתמשנו ב־sort וב־sorted בלי לשאול כיצד הן ממיינות. מיון — Sorting הוא סידור האיברים מהקטן לגדול, ויש כמה דרכים שונות להגיע לאותה תוצאה. כל דרך מבצעת כמות שונה של עבודה, ולכן שווה להכיר אותן ולהשוות ביניהן. נממש חמישה אלגוריתמים: שלושת הראשונים פשוטים אך יקרים ברשימות גדולות, הרביעי מהיר בהרבה ונשען על רקורסיה, והחמישי מהיר עוד יותר אך מתאים רק לסוג מסוים של נתונים. הפונקציות של שלושת האלגוריתמים הראשונים ממיינות את הרשימה במקומה, כמו sort; שתי האחרונות מחזירות רשימה ממוינת חדשה, כמו sorted.

מיון בחירה — Selection Sort

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

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

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

def selection_sort(numbers):
    for i in range(len(numbers)):
        min_index = i
        for j in range(i + 1, len(numbers)):
            if numbers[j] < numbers[min_index]:
                min_index = j
        numbers[i], numbers[min_index] = numbers[min_index], numbers[i]

numbers = [23, 15, 7, 89, 2, 4, 55]
selection_sort(numbers)
print(numbers)

פלט

[2, 4, 7, 15, 23, 55, 89]

כמה עבודה זה דורש? הלולאה החיצונית מבצעת n סיבובים, ובכל סיבוב הלולאה הפנימית משווה את המקום הנוכחי לכל האיברים שאחריו: n-1 השוואות בסיבוב הראשון, n-2 בשני, וכן הלאה עד השוואה אחת. סכום הסדרה הוא n(n-1)/2, כלומר בערך חצי n². בסימון סדר הגודל מתעלמים מהקבוע ואומרים שמיון בחירה הוא O(n²): הכפלת אורך הרשימה מכפילה את העבודה פי ארבעה. מספר ההשוואות אינו תלוי בסדר ההתחלתי: גם רשימה ממוינת מראש תעבור את כל ההשוואות.

מיון בועות — Bubble Sort

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

• מתחילים בזוג שבאינדקסים 0 ו־1. אם הזוג אינו מסודר, מחליפים בין השניים.
• עוברים לזוג הבא, באינדקסים 1 ו־2, ושוב מחליפים אם צריך. כך ממשיכים עד סוף הרשימה.
• כשמגיעים לסוף, האיבר הגדול ביותר נמצא במקומו הסופי: הוא „צף” לסוף במהלך המעבר.
• חוזרים למעבר נוסף מההתחלה, אך עוצרים איבר אחד לפני הסוף, כי האחרון כבר ממוין.
• אם במעבר שלם לא הייתה אף החלפה, הרשימה ממוינת ואפשר לעצור.

סרטון: אנימציה של מיון בועות

בקוד, המשתנה swapped מסמן אם הייתה החלפה במעבר הנוכחי. מאפסים אותו בתחילת כל מעבר, ואם נשאר False בסוף המעבר, יוצאים מהלולאה באמצעות break:

def bubble_sort(numbers):
    for i in range(len(numbers) - 1):
        swapped = False
        for j in range(len(numbers) - 1 - i):
            if numbers[j] > numbers[j + 1]:
                numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
                swapped = True
        if not swapped:
            break

numbers = [89, 7, 15, 3]
bubble_sort(numbers)
print(numbers)

numbers = [23, 15, 7, 19, 2, 4, 55, 6, 57, 8, 5, 1]
bubble_sort(numbers)
print(numbers)

פלט

[3, 7, 15, 89]
[1, 2, 4, 5, 6, 7, 8, 15, 19, 23, 55, 57]

בדוגמה שבתרשים, 89 צף לסוף כבר במעבר הראשון, ובכל מעבר נוסף החלק הממוין שבסוף הרשימה גדל. במקרה הגרוע, כשהרשימה ממוינת בסדר הפוך, מספר ההשוואות הוא שוב (n-1) + (n-2) + ... + 1, כלומר O(n²). היתרון של מיון בועות הוא הבדיקה swapped: רשימה שכבר ממוינת עוברת מעבר אחד בלבד בלי החלפות, והפונקציה מסיימת אחרי n-1 השוואות.

מיון הכנסה — Insertion Sort

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

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

סרטון: אנימציה של מיון הכנסה

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

def insertion_sort(numbers):
    for i in range(1, len(numbers)):
        for j in range(i, 0, -1):
            if numbers[j] < numbers[j - 1]:
                numbers[j], numbers[j - 1] = numbers[j - 1], numbers[j]
            else:
                break

numbers = [89, 7, 15, 3]
insertion_sort(numbers)
print(numbers)

numbers = [23, 15, 7, 19, 2, 4, 55, 6, 57, 8, 5]
insertion_sort(numbers)
print(numbers)

פלט

[3, 7, 15, 89]
[2, 4, 5, 6, 7, 8, 15, 19, 23, 55, 57]

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

מיזוג שתי רשימות ממוינות

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

def merge(left, right):
    i, j = 0, 0
    merged = []
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged += left[i:]
    merged += right[j:]
    return merged

print(merge([2, 4, 6, 8], [3, 4, 5, 9]))

פלט

[2, 3, 4, 4, 5, 6, 8, 9]

בכל סיבוב של הלולאה מתקדם אחד משני האינדקסים, ולכן מספר הסיבובים אינו עולה על מספר האיברים בשתי הרשימות יחד: המיזוג הוא O(n). שני הביטויים left[i:] ו־right[j:] הם חיתוכים שלמדנו בפרק א.8; אחד מהם ריק, והשני מכיל את השארית.

מיון מיזוג — Merge Sort

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

סרטון: אנימציה של מיון מיזוג

def merge_sort(numbers):
    if len(numbers) <= 1:
        return numbers
    middle = len(numbers) // 2
    left = merge_sort(numbers[:middle])
    right = merge_sort(numbers[middle:])
    return merge(left, right)

print(merge_sort([23, 15, 7, 89, 2, 4, 55, 6]))

פלט

[2, 4, 6, 7, 15, 23, 55, 89]

כמה עבודה זה דורש? בכל פיצול הרשימה מתחלקת לשניים, ולכן מספר הרמות בתרשים הוא log n. בכל רמה ממזגים את כל n האיברים, פעולה שראינו שהיא O(n). סך הכול O(n log n). ההבדל לעומת n² עצום ברשימות גדולות: עבור מיליון איברים, n² הוא מיליון מיליונים, ואילו n log n הוא כעשרים מיליון בלבד.

מיון מנייה — Counting Sort

כל האלגוריתמים עד כה השוו בין איברים. מיון מנייה — Counting Sort אינו משווה כלל, ולכן הוא מהיר יותר, אך הוא מתאים רק כשהאיברים הם מספרים שלמים לא שליליים והערך הגדול ביותר, k, ידוע ואינו גדול מדי. הרעיון:

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

def counting_sort(numbers, k):
    counts = [0] * (k + 1)
    for number in numbers:
        counts[number] += 1
    result = []
    for value in range(k + 1):
        result += [value] * counts[value]
    return result

print(counting_sort([4, 2, 4, 1, 3, 2, 0], 4))
print(counting_sort([23, 15, 7, 19, 2, 0, 4, 55, 6, 57, 8, 5, 1], 57))

פלט

[0, 1, 2, 2, 3, 4, 4]
[0, 1, 2, 4, 5, 6, 7, 8, 15, 19, 23, 55, 57]

הביטוי [value] * counts[value] יוצר רשימה שבה הערך חוזר כמספר הפעמים שנספר, ו־+= מצרף אותה לתוצאה. האלגוריתם עובר פעם אחת על הרשימה המקורית ופעם אחת על רשימת הספירה, ולכן העבודה היא O(n + k). כשטווח הערכים קטן ביחס לאורך הרשימה, זהו מיון לינארי, מהיר מכל שיטה שמשווה בין איברים. אבל כש־k ענק, למשל מספרי תעודת זהות, רשימת הספירה תהיה גדולה מהרשימה עצמה, ולמספרים ממשיים או למחרוזות השיטה אינה מתאימה כלל.

השוואה בין השיטות

אין צורך לממש מיון מחדש בכל תוכנית: sorted ו־sort של פייתון משתמשות באלגוריתם יעיל מסוג O(n log n). ההיכרות עם השיטות עוזרת להבין את העלות של הפתרון שבחרנו, ולזהות מתי כדאי למיין פעם אחת ולחפש בינארית, ומתי מספיק חיפוש לינארי פשוט. בפרק הבא נכיר דרך שלישית לחיפוש, שאינה דורשת מיון ואינה סורקת את הרשימה כלל: חישוב המיקום ישירות מתוך המפתח.