[알고리즘] Bubble Sort

Bubble Sort

서로 인접한 두 데이터의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘

---

Process

1. 첫번째 원소부터 마지막 원소까지 인접한 데이터를 비교해 조건에 맞지 않다면 서로 교환

2. 1번 수행 후엔 가장 큰 원소가 맨 뒤로 이동하게 되어 정렬에서 제외되고 (배열의 크기 - 1)만큼 반복하면 모든 데이터가 정렬됨

---

Code

numbers = []
length = 100

for i in range(length, 0, -1):
    numbers.append(i)

for _ in range(length):
    for i in range(length - 1):
        if numbers[i] > numbers[i + 1]:
            numbers[i], numbers[i + 1] = numbers[i + 1], numbers[i]

print(numbers)

---

Time Complexity

(n-1) + (n-2) + (n-3) + ... + 2 + 1 = n(n-1)/2 이므로 O(N²) 이다

매우 비효율적이기 때문에 실제 개발에는 쓰이지 않는다

---

Space Complexity

정렬하고자하는 배열안에서 교환하는 방식으로 다른 메모리 공간을 필요로 하지 않는다 (in-place sorting)

따라서 O(N) 이다

---

같은 값을 가지는 데이터의 경우 swap 연산이 이루어지지 않으므로 stable sorting 이다