Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- redirect
- shellcode
- spoofing
- arp
- Hastad
- 드림핵
- dreamhack
- RSA
- bandit
- weak key
- return address overflow
- Montgomery Reduction
- 암호학
- rao
- cryptography
- XSS
- 시스템해킹
- RSA Common Modulas Attack
- pycrpytodome
- dns
- OverTheWire Bandit Level 1 → Level 2
- picoCTF
- Bandit Level 1 → Level 2
- Franklin-Reiter Related Message Attack
- Cube Root Attack
- 웹해킹
- Crypto
- CSRF
- AES
- overthewire
Archives
- Today
- Total
암호(수학) 등.. 공부한 거 잊을거 같아서 만든 블로그
버블 정렬 (Bubble Sort) 본문
버블 정렬
버블 정렬이란?
인접한 두 원소의 크기를 비교하여 대소관계에 따라 위치를 교환하거나 교환하지 않음으로 오름차순이나 내림차순으로 데이터를 정렬하는 알고리즘이다.
예시
위의 배열을 버블정렬을 통해 오름차순으로 한번 정렬해 보자
인접한 두 값을 비교하여 큰 값이 왼쪽에 있다면 (큰 값, 작은 값) 두 개의 값의 위치를 서로 바꿔주고, 반대되는 경우 (작은 값, 큰 값) 자리를 바꾸지 않는다.
이 과정을 수행하면 배열에서 가장 큰 값이 배열의 가장 오른쪽에 위치하게 된다.
배열에 가장 큰 값인 5를 오른쪽에 옮겼던 과정을 다시 수행한다.
이때 5는 이미 제자리를 찾았으므로 비교대상에서 제외한다.
비교를 수행하여 배열에서 두 번째로 큰 값인 4가 5 다음에 위치하게 된다.
4와 5가 제자리를 찾았으므로 이 두 값을 제외한 값들을 비교하여 정렬한다.
정렬한 결과 뒤죽박죽이였던 배열의 값들이 아름답게 오름차순으로 정렬된 것을 볼 수 있다.
시간복잡도
n개의 값을 가지는 배열을 정렬한다고 가정했을 때, 가장 최악의 경우 비교 횟수는 (n - 1) + (n - 2) + (n - 3) + ....... + 1 가 된다.
1 부터 n - 1 까지의 합을 식으로 표현하면 위와 같다.
빅오 표기법으로 시간복잡도를 나타내면 최고차항이 n^2이므로 O(n^2) 이 된다.
코드 구현
# bubble_sort.py
# Time Complexity : O(n^2)
def bubble_sort(arr, result):
for i in range(len(arr)):
for j in range(len(arr) - 1 - i):
if result[j] > result[j+1]:
tmp = result[j]
result[j] = result[j + 1]
result[j + 1] = tmp
if __name__=="__main__":
number_list = list(map(int, input("Input Sequence : ").split()))
sort = number_list[:]
print("before :", number_list)
bubble_sort(number_list, sort)
print("after :", sort)
4 5 1 3 2를 입력하니 버블 정렬의 결과인 1 2 3 4 5가 출력되는 것을 볼 수 있다.
'Algorithm' 카테고리의 다른 글
[Algorithm] Montgomery Reduction Algorithm (0) | 2024.03.27 |
---|---|
이진 탐색 알고리즘 (Binary Search Algorithm) (0) | 2023.05.10 |
모듈러 거듭제곱 연산 (modular exponentiation) (0) | 2022.07.25 |
확장 유클리드 알고리즘 (Extended Euclidean Algorithm) (0) | 2022.07.18 |