[אתגר] לסדר את הבלאגן

ברשימה לצורך תרגיל זה יכולים להיות רק שלושה סוגי איברים: 1, 2 ו־3.
כתבו פונקציה בשם sort_3 שמקבלת רשימה לא מסודרת, ומסדרת את האיברים לפי ערכם בריצה אחת בלבד על הרשימה.

לדוגמה:

• עבור הרשימה [1, 2, 3, 2, 1] יוחזר [1, 1, 2, 2, 3].
• עבור הרשימה [1, 2 ,2, 2, 2, 1] יוחזר [1, 1, 2, 2, 2, 2].
• עבור הרשימה [] יוחזר [].

אסור:

• לבצע פעולות של רשימה (pop/append/insert/extend)
• ליצור רשימה חדשה

בדיקות:

import random


def check_test_case(test_case):
    try:
        result = sort_3(test_case)
    except Exception as e:
        print(f"Exception in {test_case}: {e}")
        return
    expected = sorted(test_case)
    assert result == expected, f"Problem: {result} != {expected}"


def random_checks(check_size):
    for i in range(check_size):
        test_case = random.choices([1, 2, 3], k=i)
        check_test_case(test_case)


test_cases = [
    [],
    [1],
    [2, 3],
    [3, 2],
    [1, 1, 1],
    [3, 2, 1],
    [1, 3, 2]
]
for test_case in test_cases:
    check_test_case(test_case)
random_checks(1_000)

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

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

תמונה322×559 8.17 KB

חצי כוח. כתוב במעבר אחד!

טכנית עברתי פעם אחת על הרשימה… ועוד פעם אחת על רשימה חדשה אבל אני הולכת לחפש דרך עם לולאה אחת

לולאה אחת/ לולאה מקוננת?

לולאה אחת. לולאה מקוננת זה אסון () מבחינת יעילות

מה היעילות של פעולת extend או שרשור רשימות?

עבור extend – מספר הפעולות הן כמספר האיברים שאתה מוסיף.
עבור שרשור רשימות – מספר הפעולות כגודל כמות האיברים המשורשרים (צד ימין + צד שמאל של הפלוס)

אז נשמע ש-extend יעילה יותר משרשור רשימות:

def sort_3(l):
    one = 0
    two = 0
    three = 0
    i = 0
    while i < len(l):
        if l[i] == 1:
            one += 1
        elif l[i] == 2:
            two += 1
        elif l[i] == 3:
            three += 1
        i += 1
    l=[]
    l.extend([1] * one)
    l.extend([2] * two)
    l.extend([3] * three)
    return l

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

זה אמור להשאר ליניארי גם בלולאה אחת

זה פתרון לא רע! (אקוויולנטי לזה של אורפז). אפשר אפילו טוב יותר

האם זו הכוונה? או שלא הבנתי את המטלה

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

האם פעולות כמו pop או insert מסתכלות על כל האיברים מתחילת הרשימה ככה שהפונקציה רצה מחדש על הרשימה?

כן, pop או insert מוסיפות/מסירות איבר, ומזיזות את כל האיברים לפניהם/אחריהם ברשימה אחד קדימה/אחורה

def sort_3(l):
    one = 0
    i = 0
    while i < len(l):
        if l[i] == 1:
            l.insert(0, l.pop(i))
            i += 1
            one += 1
        elif l[i] == 2:
            l.insert(one, l.pop(i))
            i += 1
        elif l[i] == 3:
            i += 1
    return l

יפה, אבל הקודם שלך היה יעיל יותר. ראה תשובתי למעלה

שימוש ב-slicing וב-pop היא אותה יעילות?

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