2. Array(배열) - Bubble Sort(버블정렬)

1. 버블정렬

- 가장 직관적이지만, 사용을 추천하지 않는 정렬 알고리즘

 

a) 버블이란?

- 배열의 2개 요소를 묶은 단위를 의미한다. 

 

b) 버블 스왑(swap)이란?

- 버블로 묶인 배열 요소 2개의 index 값을 서로 바꾸는 것을 말한다. 

array[1], array[2] = array[2], array[1]

---

2. 버블정렬의 동작방식

- 버블정렬은 배열의 요소를 정리하는 정렬 알고리즘 중 하나다.

- 배열의 요소를 2개씩 비교해서, 서로의 위치(index)를 교환(swap)하여 정리하는 방식이다. 

a) 예제를 통한 버블정렬의 이해

- 위의 예제는 오름차순으로 배열의 요소를 정리하는 버블정렬이다.

- 요소 2개씩 비교를 진행한다. 

- 요소의 크기를 비교하여 작은 수를 앞으로, 큰수를 뒤로 가도록 위치를 바꾼다.

- 비교 조건에 따라, 다르게 정렬할 수 있다.

 

b) 다음 과정

- 위의 예제 과정을 통해, 9가 가장 큰 요소임을 확인할 수 있다.

- 그러므로 9를 제외한 나머지 요소들을 대상으로 버블정렬을 수행한다. 

- 이 과정을 요소의 개수만큼 N번 반복하게 된다.

 

c) 버블정렬의 시간복잡도 → O(n^2)

- 모든 요소를 비교하면서 버블swap을 진행한다. 이는 O(n)의 시간복잡도를 갖는다. 

- 이 과정을 N번 반복한다. (n 곱하기 n)  

- 그러므로 버블 정렬은 O(n^2)의 시간복잡도를 갖는다. 

 

https://en.wikipedia.org/wiki/Bubble_sort

 

---

3. 버블정렬의 stability

- 결론부터 말하자면, 버블정렬은 안정적(stable)이다.

- 아래의 예제를 보면서, 왜 안정적인지 이해해보자. 

---

4. 버블정렬 구현하기

# bubble sort
# 1) bubble sort 개념
# bubble 이란? - 배열의 두개의 요소를 하나의 묶어 놓은 것 
# bubble swap 이란? 
#    - 어떤 기준을 기반으로 bubble로 묶인 두개의 요소를 비교한다.
#    - 비교하여 두 요소의 위치를 바꿔준다. [A, B] ==> [B, A]

# 2) bubble sort의 안정성(stability)
#   - bubble sort는 stable한 정렬 알고리즘이다. 

# 3) bubble sort의 시간복잡도(time complexity)
#   - bubble sort는 n개의 요소를 n번 탐색한다.
#   - 그러므로 O(n^2)의 시간복잡도를 갖는다. 
#   - 이와 같은 이유로 버블정렬은 잘 사용하지 않는다.

# 4) bubble sort 구현    
from typing import List

def bubble(nums: List[int]) -> List[int]:
  for idx in range(0, len(nums) - 1):
    for i in range(0, len(nums) - idx - 1):
      if nums[i] > nums[i + 1]:
        nums[i], nums[i + 1] = nums[i + 1], nums[i] #swap
  return nums

print(bubble(nums=[9,3,5,7,1])) # [1, 3, 5, 7, 9] 를 출력 

# 4) bubble sort의 안정성 확인 
def bubble2(num_str):
  for idx in range(0, len(num_str) - 1):
    for i in range(0, len(num_str) - idx - 1):
      if num_str[i][0] > num_str[i + 1][0]:
        num_str[i], num_str[i + 1] = num_str[i + 1], num_str[i] #swap
  return num_str

num_str = [(7, 'A'), (5, 'A'), (5, 'B'), (7, 'B'), (3, 'C')]
print(bubble2(num_str))

# 내가 구현한 bubble sort
case = [6, 2, 5, 1, 7, 4, 3]
for idx in range(len(case) - 1):
  for i in range(len(case) - idx - 1):
    if case[i] > case[i + 1]:
      case[i], case[i + 1] = case[i + 1], case[i]
print(case)

---

[추가 자료]

- 구현과정에서 더 자세한 코드풀이가 필요하신 분들은 아래의 글을 읽어주세요. 

 

https://devraphy.tistory.com/60

Algorithm - 버블 정렬(Bubble Sort)

---

[참고 자료]

https://youtu.be/s3FdRKHTp_o