1. Introduction 버블 정렬은 인접한 두 원소를 비교해가며 정렬하는 정렬 알고리즘이다. 구현이 매우 간단한 것으로 코딩을 처음 배우는 사람들이 주로 쓰는 알고리즘이지만, 성능이 매우 구리다. 같은 $O(n^2)$ 알고리즘 중에서도 독보적으로 느리다! 2. Approach 다음 이미지는 버블 정렬의 과정을 시각화 한 것이다. 출처는 위키피디아. 인접한 두 원소를 비교하는 과정을 정렬이 끝날 때까지 반복한다. 다행이도, 이 과정은 간단한 계산으로 $n(n-1) \over 2$안에 끝나는 것을 알 수 있다. 다음 코드는 파이썬에서 구현한 버블 정렬이다. def bubble(arr, a, b): for i in range(a, b): for j in range(a, b-i): if arr[j] > a..
버블 정렬 (Bubble Sort)
1. Introduction 버블 정렬은 인접한 두 원소를 비교해가며 정렬하는 정렬 알고리즘이다. 구현이 매우 간단한 것으로 코딩을 처음 배우는 사람들이 주로 쓰는 알고리즘이지만, 성능이 매우 구리다. 같은 $O(n^2)$ 알고리즘 중에서도 독보적으로 느리다! 2. Approach 다음 이미지는 버블 정렬의 과정을 시각화 한 것이다. 출처는 위키피디아. 인접한 두 원소를 비교하는 과정을 정렬이 끝날 때까지 반복한다. 다행이도, 이 과정은 간단한 계산으로 $n(n-1) \over 2$안에 끝나는 것을 알 수 있다. 다음 코드는 파이썬에서 구현한 버블 정렬이다. def bubble(arr, a, b): for i in range(a, b): for j in range(a, b-i): if arr[j] > a..
2020.05.23
