Wstawianie na planszy

Sortowanie przez wstawianie - Informatyka - liceum klasa 2 (Python)

Animacja pokazuje sortowanie przez wstawianie krok po kroku. **Zielona** jest część posortowana, **czerwony** element właśnie wstawiany, a **pomarańczowy** element przesunięty o jedno miejsce w prawo, żeby zrobić mu miejsce. Gdy wstawiany element trafia na swoje miejsce, zielona część rośnie o jeden słupek. Porównaj z sortowaniem bąbelkowym: tam na końcu rosła część z największymi elementami, tu na początku rośnie część posortowana, ale jeszcze nie ostateczna.

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

values = [6, 2, 8, 4, 9, 1, 5]

class InsertionSort(Sprite):
    def __init__(self):
        self.visible = False
        self.i = 1
        self.j = 0
        self.x = values[1]
        self.wait = 0

    def update(self):
        self.wait += 1
        if self.wait < 15:
            return
        self.wait = 0
        n = len(values)
        if self.i >= n:
            draw(values, [(22, 163, 74)] * n)
            world.stop()
            return
        colors = [(22, 163, 74)] * (self.i + 1) + [(99, 102, 241)] * (n - self.i - 1)
        if self.j >= 0 and values[self.j] > self.x:
            values[self.j + 1] = values[self.j]
            values[self.j] = self.x
            colors[self.j + 1] = (234, 88, 12)
            colors[self.j] = (220, 38, 38)
            self.j -= 1
        else:
            colors[self.j + 1] = (220, 38, 38)
            self.i += 1
            if self.i < n:
                self.x = values[self.i]
                self.j = self.i - 1
        draw(values, colors)

draw(values)
world.add(InsertionSort())
world.start()

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

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