[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
Posted by J-sean
:

[Algorithm Training] Digital Number Display 디지털 숫자 표시

Algorithm Training 2020. 10. 2. 20:46 |
반응형

숫자(1~99,999)와 디스플레이 크기(1~10) s를 입력하면 [(2s+3)행 X (s+2)열] 크기의 디지털 숫자로 표시하는 프로그램을 만들어 보자. 각 숫자 사이에는 1줄의 공백이 있다.


숫자 5,238을 s=1의 크기로 표시한 예.


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
#include <iostream>
 
using namespace std;
 
int main()
{
    const int MAX_DIGIT = 5;
    const int MAX_SCALE = 10;
 
    char hor_bar[2][MAX_SCALE + 1] = { {"          "}, {"----------"} };
    char ver_bar[2][2] = { {" "}, {"|"} };
 
    char hor_dig[10][3] = { {1, 0, 1}, {0, 0, 0}, {1, 1, 1}, {1, 1, 1}, {0, 1, 0},
        {1, 1, 1}, {1, 1, 1}, {1, 0, 0}, {1, 1, 1}, {1, 1, 1} };    // 0~9
    char ver_dig[10][4] = { {1, 1, 1, 1}, {0, 1, 0, 1}, {0, 1, 1, 0}, {0, 1, 0, 1}, {1, 1, 0, 1},
        {1, 0, 0, 1}, {1, 0, 1, 1}, {0, 1, 0, 1}, {1, 1, 1, 1}, {1, 1, 0, 1} };    // 0~9
    //  -
    // | |
    //  -
    // | |
    //  -
    // 1 digit = 가로선 3개(3줄), 세로선 4개(2줄)
    //             최소 5행 3열
 
    char digits[5][(MAX_SCALE + 3) * MAX_DIGIT] = { '\0', };    // 각 숫자 사이에 빈칸 + 마지막 개행 문자 = MAX_SCALE + 3.
                                                                // null문자 '\0'으로 초기화.
    char number[MAX_DIGIT + 1];
    cout << "Enter number(1~99,999): ";
    cin >> number;
 
    int scale;
    cout << "Enter scale(1~10): ";
    cin >> scale;
 
    // scale에 맞게 가로선 길이 조정.
    hor_bar[0][scale] = '\0';
    hor_bar[1][scale] = '\0';
 
    int count_number = strlen(number);
 
    for (int i = 0; i < count_number; i++)
    {
        int real_number = number[i] - '0';    // 문자를 숫자로 변환.
 
        // 두 번째 숫자부터 각 숫자마다 빈 칸 삽입.
        if (i > 0)
            for (int j = 0; j < 5; j++)
                strcat_s(digits[j], sizeof(digits[j]), " ");
 
        // 첫 번째 줄 삽입.
        strcat_s(digits[0], sizeof(digits[0]), " ");
        strcat_s(digits[0], sizeof(digits[0]), hor_bar[hor_dig[real_number][0]]);
        strcat_s(digits[0], sizeof(digits[0]), " ");
 
        // 두 번째 줄 삽입.
        strcat_s(digits[1], sizeof(digits[1]), ver_bar[ver_dig[real_number][0]]);
        strcat_s(digits[1], sizeof(digits[1]), hor_bar[0]);
        strcat_s(digits[1], sizeof(digits[1]), ver_bar[ver_dig[real_number][1]]);
 
        // 세 번째 줄 삽입.
        strcat_s(digits[2], sizeof(digits[2]), " ");
        strcat_s(digits[2], sizeof(digits[2]), hor_bar[hor_dig[real_number][1]]);
        strcat_s(digits[2], sizeof(digits[2]), " ");
 
        // 네 번째 줄 삽입.
        strcat_s(digits[3], sizeof(digits[3]), ver_bar[ver_dig[real_number][2]]);
        strcat_s(digits[3], sizeof(digits[3]), hor_bar[0]);
        strcat_s(digits[3], sizeof(digits[3]), ver_bar[ver_dig[real_number][3]]);
 
        // 다섯 번째 줄 삽입.
        strcat_s(digits[4], sizeof(digits[4]), " ");
        strcat_s(digits[4], sizeof(digits[4]), hor_bar[hor_dig[real_number][2]]);
        strcat_s(digits[4], sizeof(digits[4]), " ");
    }
 
    // 첫 번째 줄 출력
    cout << digits[0] << endl;
 
    // 두 번째 줄 출력
    for (int i = 0; i < scale; i++)
        cout << digits[1] << endl;
 
    // 세 번째 줄 출력
    cout << digits[2] << endl;
 
    // 네 번째 줄 출력
    for (int i = 0; i < scale; i++)
        cout << digits[3] << endl;
 
    // 다섯 번째 줄 출력
    cout << digits[4] << endl;
 
    return 0;
}


잘못된 입력에 대한 처리는 생략되어 있다.


실행 결과.



반응형
저작자표시 비영리 변경금지

'Algorithm Training' 카테고리의 다른 글

[Algorithm Training] Minesweeper 지뢰찾기 맵 만들기  (2) 2020.10.01
Posted by J-sean
:

[Algorithm Training] Minesweeper 지뢰찾기 맵 만들기

Algorithm Training 2020. 10. 1. 09:50 |
반응형


지뢰 찾기는 MXN 크기의 지뢰밭에서 모든 지뢰의 위치를 찾는 게임이다. 이 게임의 각 셀은 인접한 최대 8개의 셀 중 몇 개의 셀에 지뢰가 있는지 보여준다.


아래와 같이 맵의 크기를 입력하고 지뢰의 위치를 #로 입력하면 게임 맵을 작성해 주는 프로그램을 만들어 보자.



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
#include <iostream>
 
using namespace std;
 
int main()
{
    int row, column;
 
    cout << "Enter minefield size(row column): ";
    cin >> row >> column;
 
    char** field = new char* [row];
    for (int i = 0; i < row; i++)
    {
        field[i] = new char[column];
        //memset(field[i], 0, sizeof(char) * (column));
    }
 
    char line[100];
 
    cout << "Enter minefield(# = mine): " << endl;
    for (int i = 0; i < row; i++)
    {
        cin >> line;        
        memcpy_s(field[i], column, line, strlen(line) > (unsigned)column ? column : strlen(line));
        // Invalid input prevention.
    }
 
    char** map = new char* [row];
    for (int i = 0; i < row; i++)
    {
        map[i] = new char[column];
        memset(map[i], '0', sizeof(char) * (column));
    }
 
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < column; j++)
        {
            if (field[i][j] == '#')
            {
                map[i][j] = '#';
            }
            else
            {
                for (int k = i - 1; k < i + 2; k++)
                    for (int l = j - 1; l < j + 2; l++)
                        if (k > -1 && k < row && l > -1 && l < column && field[k][l] == '#')
                            map[i][j]++;
            }
        }
    }
 
    cout << endl << endl << "Minefield map: " << endl;
 
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < column; j++)
        {
            cout << map[i][j] << ' ';
        }
        cout << endl;
    }
 
    for (int i = 0; i < row; i++)
    {
        delete[] field[i];
    }
    delete[] field;
 
    for (int i = 0; i < row; i++)
    {
        delete[] map[i];
    }
    delete[] map;
 
    return 0;
}



알고리즘은 간단하다. 각 셀에서 주변의 모든 셀을 검사해 지뢰가 있으면 숫자를 증가 시킨다. 모서리에 위치한 셀은 주변 셀을 검사할 때 배열의 범위를 넘어가지 않도록 주의 한다.


실행 결과.


반응형
저작자표시 비영리 변경금지

'Algorithm Training' 카테고리의 다른 글

[Algorithm Training] Digital Number Display 디지털 숫자 표시  (2) 2020.10.02
Posted by J-sean
:

티스토리툴바