[Algorithm] 버블 정렬 - Bubble Sort (Python)

📌 버블 정렬

버블 정렬은 코드가 반복하면서 배열의 원소가 뒷쪽으로 밀려나는 모습이 마치 거품이 떠오르는 모습과 같다고 하여 붙여진 이름이다.

Stable Sort이면서 In-place Sort인 버블 정렬은 다른 정렬에 비해 속도가 느리지만, 구현이 간단하여 자주 사용되곤 한다.

아이디어

1. 배열의 i번째 인덱스와 i+1번째 인덱스의 키를 비교한다.
2. i번째 인덱스의 키가 더 크다면 자리를 상호 교환(swap)한다.
3. 위 과정을 반복수행한다.

복잡도 분석

• 선택 정렬과 마찬가지로 배열 내에서만 값의 이동이 이루어지기 때문에 O(1)의 공간 복잡도를 갖는다.
  
  
• 각 순회마다 비교 대상이 하나씩 줄어들기 때문에, 비교하는 데에 소모되는 시간은 다음과 같다.
  
  (N-1) + (N-2) + ... + 2 + 1 = N * (N -1) / 2
  
  따라서 비교 과정에서 총 O(N^2) 만큼의 시간을 소모한다. 또한, 최악의 경우에 비교할 때마다 교환이 발생하므로 교환 횟수도 비교 횟수와 마찬가지로 O(N^2)가 된다.
  결국, 버블 정렬은 총 O(N^2)만큼의 시간 복잡도를 갖는다.
  
  

특징

👍 장점

• 구현이 간단하다.
• 데이터를 하나씩 비교하기 때문에 정밀한 비교가 가능하다.

👎 단점

• 데이터를 전부 비교해야 하므로 시간 효율이 좋지 않다.

구현

arr = [4, 6, 1, 7, 2, 9, 3]

n = len(arr)

for i in range(n-1, 0, -1):
	for j in range(i):
		if arr[j] > arr[j+1]:
			arr[j], arr[j+1] = arr[j+1], arr[j]

--

참고 사이트

🙇🏻‍♂️ https://bowbowbow.tistory.com/10