동작 방식
- 배열의 바로 다음값과 비교해서 큰값을 뒤로 자리를 바꿔준다
- 해당 작업을 처음부터 끝까지 한번 진행하면 맨뒤에 가장 큰 값이 간다.
- 그러므로 그다음은 위 작업을 마지막 배열 전까지 작업을 한다.
- 해당 작업을 반복하면 정렬이 이루어 진다.
단점
- 선택정렬보다 효율이 엄청 떨어짐 (자리를 바꾸는 작업이 훨씬 더 많기 때문.)
시간 복잡도
O(N*N)
- 추론 1 : 10 + 9 + 8 ... +1 번 비교 작업
- 추론 2 : N(N+1)/2
- 추론 3 : '/2'는 N이 엄청 큰 수라고 가정 했을 경우 의미 없는 값으로 처리한다
- 결론 : 시간 복잡도는 N*N
동작 순서 예시
[5, 1, 8, 4, 3, 2, 9, 6, 7, 10]
[1, 5, 4, 3, 2, 8, 6, 7, 9, 10]
[1, 4, 3, 2, 5, 6, 7, 8, 9, 10]
[1, 3, 2, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
python 구현
'''
@ Author : bsh0817
@ Created : 2020. 01. 24
@ Update : 2020. 01. 24
@ Description : Bubble sort (버블 정렬)
'''
def fn_swapping(list_target, int_index_a, int_index_b):
'''
@Description: List index swapping
@Arguments Example
list_target = [10, 5, 1, 8, 4, 3, 2, 9, 6, 7]
int_index_a = 0
int_index_b = 2
'''
value_tmp = list_target[int_index_a]
list_target[int_index_a] = list_target[int_index_b]
list_target[int_index_b] = value_tmp
return list_target
def fn_bubble_sort(list_input):
'''
@Description: Bubble sort (버블 정렬)
@Arguments Example
list_input = [10, 5, 1, 8, 4, 3, 2, 9, 6, 7]
'''
int_len_list_input = len(list_input)
for int_list_input_index in range(int_len_list_input):
for int_index in range(0, int_len_list_input - int_list_input_index -1):
if list_input[int_index + 1] < list_input[int_index]:
list_input = fn_swapping(list_input, int_index, int_index + 1)
print(list_input)
if __name__ == "__main__":
list_fn_bubble_sort_param = [10, 5, 1, 8, 4, 3, 2, 9, 6, 7]
fn_bubble_sort(list_fn_bubble_sort_param)