AnimatedAlgorithms/algorithms/insertion_sort.py at main · Al-Madina/AnimatedAlgorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
"""
Animated insertion sort
"""

__author__ = "Ahmed Hassan"
__license__ = "MIT"
__email__ = "ahmedhassan@aims.ac.za"

import random
import sys
import time

import pygame
from utils import draw_array, animate_swap

pygame.init()

screen_width, screen_height = 1200, 400
screen = pygame.display.set_mode((screen_width, screen_height))
pygame.display.set_caption("Insertion Sort Animation")

# Font
font = pygame.font.Font(None, 36)

BLACK = (0, 0, 0)
BLUE = (58, 148, 255)
LIGHT_BLUE = (170, 214, 255)
WHITE = (255, 255, 255)
RED = (255, 0, 0)
GOLDEN_YELLOW = (255, 215, 0)
GREEN = (50, 205, 50)


# The number of array elements
num_elements = 10
array = [random.randint(1, 99) for _ in range(num_elements)]

# Uncomment the line below to see the best-case scenario (when the array is already sorted)
# array = sorted(array)

# Uncomment the line below to see the worst-case scenario (when the array is sorted in descending order)
# array = sorted(array, reverse=True)

sorted_array = []
rect_width = screen_width // num_elements
rect_height = 100

y = (screen_height - rect_height) // 2

# Control animation speed
clock = pygame.time.Clock()
speed = 720  # frame rate
delay = 0.5  # seconds


def insertion_sort(array):
    draw_array(
        array,
        screen,
        y,
        rect_width,
        rect_height,
        clock,
        speed,
        font,
        highlight_indexes=[0],
    )
    time.sleep(delay)
    for j in range(1, len(array)):
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                pygame.quit()
                sys.exit()

        key = array[j]
        draw_array(
            array,
            screen,
            y,
            rect_width,
            rect_height,
            clock,
            speed,
            font,
            highlight_indexes=list(range(j)),
            highlight_color=GREEN,
        )
        time.sleep(delay)

        draw_array(
            array,
            screen,
            y,
            rect_width,
            rect_height,
            clock,
            speed,
            font,
            highlight_indexes=[j],
        )
        time.sleep(delay)
        i = j - 1
        while i >= 0 and array[i] > key:
            for event in pygame.event.get():
                if event.type == pygame.QUIT:
                    pygame.quit()
                    sys.exit()
            animate_swap(
                array,
                i,
                i + 1,
                y,
                screen,
                rect_width,
                rect_height,
                clock,
                speed,
                font,
            )
            time.sleep(0.5 * delay)
            i -= 1
        array[i + 1] = key

    draw_array(
        array,
        screen,
        y,
        rect_width,
        rect_height,
        clock,
        speed,
        font,
        highlight_indexes=list(range(len(array))),
        highlight_color=GREEN,
    )


def main():
    running = True
    insertion_sort(array)

    while running:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                running = False

    pygame.quit()


if __name__ == "__main__":

    main()