אלגוריתמי מיון

אלגוריתמי מיון

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

לדוגמה, אני משתמש בפירות בגדלים שונים.

ייצוג פירות עם גדלים:

נתאים פירות לגדלים. נשתמש בטאפלים (tuple), כאשר:

• האלמנט הראשון – זהו גודל הפרי:
  • 🍎 (קטן) – תפוח
  • 🍐 (בינוני) – אגס
  • 🍉 (גדול) – אבטיח
  • 🧺 (גדול מאוד) – סלסלה
• האלמנט השני – זהו מזהה ייחודי, לצורך פעולת התוכנית.

דוגמה: (🍎, 1) – זהו תפוח קטן עם מזהה 1.

from typing import List, Tuple

def compare_fruits(fruit1: Tuple[str, int], fruit2: Tuple[str, int]) -> int:
    """
    משווה שני פירות לפי גודל.

    Args:
        fruit1: טאפל (גודל, מזהה).
        fruit2: טאפל (גודל, מזהה).

    Returns:
        -1, אם fruit1 קטן מ-fruit2, 1, אם fruit1 גדול מ-fruit2, 0, אם שווים.
    """
    order = {"🍎": 0, "🍐": 1, "🍉": 2, "🧺": 3}  # מגדיר את סדר הפירות לפי גודל
    size1 = order.get(fruit1[0]) # מקבל את גודל הפרי הראשון
    size2 = order.get(fruit2[0]) # מקבל את גודל הפרי השני
    if size1 < size2: # אם גודל הפרי הראשון קטן יותר, מחזיר -1
        return -1
    elif size1 > size2: # אם גודל הפרי הראשון גדול יותר, מחזיר 1
        return 1
    else: # אם הגדלים שווים, מחזיר 0
      return 0

אלגוריתמי מיון (השוואה לפי גודל פרי):

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

graph TD
    A[התחלה] --> B{האם יש פירות לא ממוינים?};
    B -- כן --> C[השווה שני פירות סמוכים];
    C -- הראשון גדול יותר --> D[החלף מקומות];
    D --> E[עבור לזוג הבא];
    C -- הראשון לא גדול יותר --> E;
    E --> F{האם הגיע לסוף הרשימה?};
    F -- לא --> C;
    F -- כן --> G{האם הייתה החלפה?};
    G -- כן --> B;
    G -- לא --> H[סיום];
    B -- לא --> H;
    H[סיום]

def bubble_sort(fruits: List[Tuple[str, int]]) -> List[Tuple[str, int]]:
    """
    ממיין רשימת פירות לפי גודל, באמצעות אלגוריתם "מיון בועות".

    Args:
        fruits: רשימת טאפלים (גודל, מזהה).

    Returns:
        רשימת טאפלים ממוינת.
    """
    n = len(fruits)  # מקבל את מספר הפירות
    for i in range(n):  # עובר על הרשימה n פעמים
        for j in range(0, n - i - 1):  # עובר על החלק הלא ממוין של הרשימה
            if compare_fruits(fruits[j], fruits[j + 1]) == 1:  # אם הפרי משמאל גדול יותר מהפרי מימין
                fruits[j], fruits[j + 1] = fruits[j + 1], fruits[j]  # מחליף מקומות
    return fruits

2. מיון הכנסה (Insertion Sort):
   • האלגוריתם בונה רשימה ממוינת, על ידי הוספת פירות אחד אחד. פרי חדש מוכנס למקום הנכון, כדי לשמור על הסדר לפי גודל.
   • מיון הכנסה טוב לרשימות קטנות או לאלו שבהן הנתונים כבר כמעט ממוינים.
3. מיון בחירה (Selection Sort):
   • האלגוריתם מוצא את הפרי הקטן ביותר בחלק הלא ממוין של הרשימה. לאחר מכן הוא מציב את הפרי הזה במקום הראשון בחלק הלא ממוין של הרשימה.
   • תהליך זה חוזר על עצמו עד שכל הפירות ממוינים.
   • מיון בחירה פשוט, אך לא יעיל לרשימות גדולות.

def insertion_sort(fruits: List[Tuple[str, int]]) -> List[Tuple[str, int]]:
    """
    ממיין רשימת פירות לפי גודל, באמצעות אלגוריתם "מיון הכנסה".

    Args:
        fruits: רשימת טאפלים (גודל, מזהה).

    Returns:
        רשימת טאפלים ממוינת.
    """
    for i in range(1, len(fruits)): # מתחיל מהפרי השני (הראשון נחשב ממוין)
        key = fruits[i] # לוקח את הפרי הבא
        j = i - 1 # אינדקס הפרי הקודם
        while j >= 0 and compare_fruits(fruits[j], key) == 1: # מחפש מיקום בחלק הממוין, לאן להכניס את הפרי
            fruits[j + 1] = fruits[j] # מזיז פירות כדי לפנות מקום לחדש
            j -= 1
        fruits[j + 1] = key # מכניס את הפרי למקום הנכון
    return fruits

def selection_sort(fruits: List[Tuple[str, int]]) -> List[Tuple[str, int]]:
    """
    ממיין רשימת פירות לפי גודל, באמצעות אלגוריתם "מיון בחירה".

    Args:
        fruits: רשימת טאפלים (גודל, מזהה).

    Returns:
        רשימת טאפלים ממוינת.
    """
    n = len(fruits) # מקבל את מספר הפירות ברשימה
    for i in range(n): # עובר על כל הפירות ברשימה
        min_index = i # אינדקס הפרי הקטן ביותר
        for j in range(i + 1, n): # מחפש את הפרי הקטן ביותר בחלק הלא ממוין
            if compare_fruits(fruits[j], fruits[min_index]) == -1: # אם נמצא פרי קטן יותר מהמינימום הנוכחי
                min_index = j # זוכר את אינדקס המינימום החדש
        fruits[i], fruits[min_index] = fruits[min_index], fruits[i] # מחליף את הפרי הנוכחי עם הקטן ביותר מהחלק הלא ממוין
    return fruits

def display_fruits(fruits: List[Tuple[str, int]]) -> str:
    """
    ממיר רשימת פירות למחרוזת להצגה.

    Args:
        fruits: רשימת טאפלים (גודל, מזהה).

    Returns:
        מחרוזת להצגת רשימת הפירות.
    """
    return ", ".join(f"{fruit[0]}{fruit[1]}" for fruit in fruits)  # מרכיב מחרוזת להדפסה


# יוצר רשימת פירות למיון
fruits = [
    ("🍉", 1), ("🍎", 2), ("🍐", 3), ("🧺", 4), ("🍎", 5), ("🍉", 6), ("🍐", 7),
    ("🍎", 8), ("🧺", 9), ("🍉", 10), ("🍐", 11), ("🍎", 12)
]

print("רשימת פירות מקורית: " + display_fruits(fruits))  # מדפיס את הרשימה המקורית
print("דוגמאות: תפוח (🍎) < אגסים (🍐) < אבטיח (🍉) < סלסלות (🧺)")  # מציג את סדר הפירות

# מיון בועות
sorted_fruits_bubble = bubble_sort(fruits.copy()) # ממיין עותק של הרשימה
print("מיון בועות: " + display_fruits(sorted_fruits_bubble)) # מדפיס את התוצאה

# מיון הכנסה
sorted_fruits_insertion = insertion_sort(fruits.copy()) # ממיין עותק של הרשימה
print("מיון הכנסה: " + display_fruits(sorted_fruits_insertion)) # מדפיס את התוצאה

# מיון בחירה
sorted_fruits_selection = selection_sort(fruits.copy()) # ממיין עותק של הרשימה
print("מיון בחירה: " + display_fruits(sorted_fruits_selection)) # מדפיס את התוצאה

הסבר קוד:

1. compare_fruits(fruit1, fruit2): פונקציה זו משווה שני פירות לפי גודל ומחזירה -1 אם הפרי הראשון קטן יותר, 1 אם גדול יותר, ו-0 אם הם שווים. אני משתמש במילון order כדי להגדיר את סדר גודל הפירות.
2. bubble_sort(fruits): אני מיישם את אלגוריתם מיון בועות, שבו פירות סמוכים מושווים ומוחלפים אם הם בסדר שגוי.
3. insertion_sort(fruits): אני מיישם את אלגוריתם מיון הכנסה, שבו כל פרי חדש מוכנס למקום הנכון בחלק הממוין כבר של הרשימה.
4. selection_sort(fruits): אני מיישם את אלגוריתם מיון בחירה, שבו בכל מעבר אני מוצא את הפרי הקטן ביותר ומציב אותו במקום הנכון.
5. display_fruits(fruits): פונקציה זו ממירה רשימת פירות למחרוזת לצורך פלט נוח.
6. דוגמאות: בסוף, אני יוצר רשימת פירות ומיישם עליה את כל שלושת אלגוריתמי המיון, ומדפיס את תוצאות כל אחד מהם. אני גם מראה לך את הסדר שבו הפירות ממוינים.