[Pygame] Sorting Algorithms in Python 파이썬 정렬 알고리즘 1
Python 2024. 3. 9. 19:10 |반응형
기본 정렬 알고리즘 네 가지(선택, 버블, 삽입, 셸)를 파이게임으로 시각화 해 보자.
|
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
153
154
155
156
157
158
159
160
|
import os
import random
os.environ['PYGAME_HIDE_SUPPORT_PROMPT'] = '1'
import pygame
pygame.init()
pygame.display.set_caption("Sorting Visualization")
screensize = (640, 580)
screen = pygame.display.set_mode(screensize)
clock = pygame.time.Clock()
framerate = 10
running = True
font = pygame.font.Font(None, 30)
text = font.render("Sorting Visualization\n\n" +
"*s: Selection Sorting [ O(n^2) ]\n" +
"*b: Bubble Sorting [ O(n^2) ]\n" +
"*i: Insertion Sorting [ O(n^2) ]\n" +
"*h: Shell Sorting [ O(n^2) ]\n" +
"\n*g: Random Data Generation", True, "gray")
text_pos = text.get_rect()
text_pos.center = (screen.get_width()/2, text_pos.height/2)
data_size = 64
data = list()
data_color = list()
def DataGenerator():
global data
global data_color
data = [random.randint(10, 400) for i in range(data_size)]
data_color = [(random.randint(0, 255), random.randint(0, 255), random.randint(0, 255))
for i in range(data_size)]
DataGenerator()
def Visualize():
screen.fill("black")
screen.blit(text, text_pos)
for i in range(data_size):
pygame.draw.rect(screen, data_color[i], (i*10, screensize[1]-data[i], 10, data[i]))
pygame.display.flip()
clock.tick(framerate)
def Finalize():
screen.fill("white")
pygame.display.flip()
clock.tick(framerate)
def EventHandler():
# 이벤트 처리하는 코드가 없으면 정렬시 프로그램이 freeze된다.
for event in pygame.event.get():
if event.type == pygame.KEYDOWN and event.key == pygame.K_ESCAPE:
return -1 # 정렬 중지.
elif event.type == pygame.QUIT:
exit() # 프로그램 종료.
def SelectSort():
for i in range(data_size-1):
if EventHandler() == -1:
return
min = i
for j in range(i+1, data_size, 1):
if data[min] > data[j]:
min = j
data[i], data[min] = data[min], data[i]
data_color[i], data_color[min] = data_color[min], data_color[i]
Visualize()
Finalize()
def BubbleSort():
for i in range(data_size-1):
if EventHandler() == -1:
return
sorted = True
for j in range(data_size-1-i):
if data[j] > data[j+1]:
data[j], data[j+1] = data[j+1], data[j]
data_color[j], data_color[j+1] = data_color[j+1], data_color[j]
sorted = False
if sorted == True:
break
Visualize()
Finalize()
def InsertSort():
for i in range(1, data_size, 1):
if EventHandler() == -1:
return
val = data[i]
colval = data_color[i]
for j in range(i, 0, -1):
if data[j-1] > val:
data[j] = data[j-1]
data_color[j] = data_color[j-1]
j = j-1
else:
break
data[j] = val
data_color[j] = colval
Visualize()
Finalize()
def ShellSort():
# 점화식 리스트 만들기
recurrence = [1]
while(True):
next = recurrence[-1]*3+1
if next < data_size:
recurrence.append(next)
else:
recurrence.reverse()
break
for D in recurrence:
for i in range(D, data_size, 1):
if EventHandler() == -1:
return
val = data[i]
colval = data_color[i]
j = i
while True:
if j>=D and data[j-D]>val:
data[j] = data[j-D]
data_color[j] = data_color[j-D]
j = j-D
else:
break
data[j] = val
data_color[j] = colval
Visualize()
Finalize()
while running:
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
elif event.type == pygame.KEYDOWN and event.key == pygame.K_ESCAPE:
running = False
elif event.type == pygame.KEYDOWN and event.key == pygame.K_s:
SelectSort()
elif event.type == pygame.KEYDOWN and event.key == pygame.K_b:
BubbleSort()
elif event.type == pygame.KEYDOWN and event.key == pygame.K_i:
InsertSort()
elif event.type == pygame.KEYDOWN and event.key == pygame.K_h:
ShellSort()
elif event.type == pygame.KEYDOWN and event.key == pygame.K_g:
DataGenerator()
Visualize()
|
코드를 작성하고 실행한다.
※ 참고
2024.03.22 - [Python] - [Pygame] Sorting Algorithms in Python 파이썬 정렬 알고리즘 2
알고리즘_03_강의록.pdf
1.02MB
알고리즘_04_강의록.pdf
1.86MB
반응형
'Python' 카테고리의 다른 글
| [Pygame] Sorting Algorithms in Python 파이썬 정렬 알고리즘 2 (0) | 2024.03.22 |
|---|---|
| [Pygame] Pygame Gravity 파이게임 중력 (0) | 2024.02.03 |
| [Pygame] Pygame Simple Camera 파이게임 간단한 카메라 (0) | 2024.02.02 |
| [Pygame] Pygame GUI 파이게임 그래픽 유저 인터페이스 (0) | 2024.01.29 |
| [Pygame] Box2D 파이게임 물리 라이브러리 (0) | 2024.01.28 |