버블 정렬이란?
- 두 인접한 데이터를 비교해서, 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘
단계별로 생각하기
- 예 : data_list = [9, 4, 1, 5]
- n개의 리스트가 있는 경우 최대 n-1번의 로직 적용
- 로직을 1번 적용할 때마다 큰 숫자가 뒤에서 1개씩 결정
- 데이터 교환이 없으면 로직을 반복 적용할 필요 없음
- 1차 로직
- 2차 로직
- 3차로직
알고리즘 구현
def bubble_sort(data):
for index in range(len(data) - 1): # 로직 횟수
swap == False
for index2 in range(len(data) - index - 1): # 로직 1회 할 때마다 뒤에 수가 결정되므로
if data[index2] > data[index2 + 1]:
data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
swap == True
if swap == False:
break
return data
data_list = [9, 4, 1, 5]
print(bubble_sort(data_list)) # [1, 4, 5, 9]
정리
- 비교연산에 대한 빅-오는 최악의 경우와 최선의 경우 구분 없이 O(n^2)이다.
'Algorithm & Data Structure > Algorithm' 카테고리의 다른 글
[알고리즘] 동적 계획법 (Dynamic Programming)과 분할 정복 (Divide and Conquer) (0) | 2020.06.16 |
---|---|
[알고리즘] 재귀 용법 (recursive call) (0) | 2020.06.16 |
[알고리즘] 선택 정렬 (selection sort) (0) | 2020.06.16 |
[알고리즘] 삽입 정렬 (insertion sort) (0) | 2020.06.15 |