Wykres porównań obu metod

Porównanie metod sortowania: liczba porównań i zamian - Informatyka - technikum klasa 1 (Python)

Wykres zestawia liczbę porównań obu metod dla czterech rodzajów danych: para słupków na każde dane, **niebieski** = bąbelkowe, **zielony** = wstawianie (wysokość = liczba porównań podzielona przez 5). Od lewej: posortowane, prawie posortowane, wymieszane, odwrotne. Przy danych odwrotnych obie metody wykonują tyle samo porównań: to dla obu przypadek pesymistyczny.

arrow = Sprite()
arrow.image = 16
arrow.size = 10
world.add(arrow)
arrow.visible = False
def draw(values, colors=None):
    world.clear_trails()
    for i, v in enumerate(values):
        if colors:
            arrow.pen.color = colors[i]
        else:
            arrow.pen.color = (99, 102, 241)
        arrow.pen.on = False
        arrow.position = (-90 + 14 * i, -80)
        arrow.angle = 0
        arrow.pen.on = True
        for side in [8 * v, 10, 8 * v, 10]:
            arrow.move(side)
            arrow.turn(90)
    arrow.pen.on = False

def bubble_stats(values):
    values = list(values)
    n = len(values)
    comparisons = 0
    swaps = 0
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            comparisons += 1
            if values[j] > values[j + 1]:
                values[j], values[j + 1] = values[j + 1], values[j]
                swaps += 1
                swapped = True
        if not swapped:
            break
    return comparisons, swaps

def insertion_stats(values):
    values = list(values)
    comparisons = 0
    shifts = 0
    for i in range(1, len(values)):
        x = values[i]
        j = i - 1
        while j >= 0:
            comparisons += 1
            if values[j] > x:
                values[j + 1] = values[j]
                shifts += 1
                j -= 1
            else:
                break
        values[j + 1] = x
    return comparisons, shifts

DATA = [
    ("posortowane", [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]),
    ("prawie", [1, 2, 4, 3, 5, 6, 8, 7, 9, 10]),
    ("wymieszane", [7, 2, 9, 4, 10, 1, 6, 3, 8, 5]),
    ("odwrotne", [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]),
]

values = []
colors = []
for name, data in DATA:
    values.append(bubble_stats(data)[0] / 5)
    values.append(insertion_stats(data)[0] / 5)
    colors.append((99, 102, 241))
    colors.append((22, 163, 74))
draw(values, colors)

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Informatyka - technikum klasa 1·Zaloguj się, aby zapisać postęp na koncie.