버블 정렬 (Bubble Sort)
목차
두 인접한 데이터를 비교하여, 큰 값을 뒤로 바꾸는 정렬 알고리즘.
동작 방식
- n개의 리스트가 있을 경우 n-1번의 로직이 필요
- 로직을 1회 적용할 때마다 가장 큰 수가 뒤에서부터 1개씩 정렬
- 이미 정렬된 경우 일찍 종료 가능
구현
def bubble_sort(data):
data_len = len(data)
for index in range(data_len - 1):
swap_flag = False
for bubble in range(data_len - index - 1):
if data[bubble] > data[bubble + 1]:
data[bubble], data[bubble + 1] = data[bubble + 1], data[bubble]
swap_flag = True
if not swap_flag:
break
return data시간 복잡도
| 경우 | 복잡도 |
|---|---|
| 일반 | O(n²) |
| 최악 | n*(n-1)/2 |
| 완전 정렬 상태 | O(n) |