알고리즘/[Python] 알고리즘
(Python) 버블 정렬(bubble sort)
maengjh
2020. 2. 4. 21:06
(Python) 버블 정렬(bubble sort)¶
버블 정렬(bubble sort)란?
- 서로 인접한 두 원소들을 순차적으로 비교하여 정렬하는 알고리즘이다.
(인접해 있는 두 원소의 크기가 순서에 맞지 않다면 서로 교환한다.)
In [1]:
from IPython.display import Image
Image("img/bubble_sort.png")
Out[1]:
버블 정렬(bubble)의 시간복잡도
- 비교 횟수
- best, average, worst가 모두 일정하다.
- n-1, n-2, n-3, ... , 2, 1번 비교하므로 총 n(n-1)/2번 비교한다.
- 교환 횟수
- 입력 자료가 이미 정렬되어 있는 경우라면, 자료의 이동이 일어나지 않는다.
- 최악의 경우는 입력 자료가 역순으로 정렬되어 있는 경우이다.
두 항목을 서로 교환해주기 위해선 3번의 이동작업이 필요하다.
따라서, 3n(n-1)/2번 발생한다.
시간복잡도
- Best : n제곱
- Average : n제곱
- Worst : n제곱
In [2]:
# 배열에서 인접한 두 항목을 서로 교환하는 함수
def swap_f(index_a, index_b, array):
t = array[index_a]
array[index_a] = array[index_b]
array[index_b] = t
In [3]:
def bubble_sort(array):
j = len(array)
for _ in range(len(array)-1):
i = 0
j = j-1
for x in range(j):
print(array)
if array[i] > array[i+1]:
swap_f(i, i+1, array)
i = i+1
return array
In [4]:
bubble_sort([4,3,2,1])
Out[4]: