정렬 알고리즘 1 - 버블 정렬(bubble sort)

버블 정렬은 배열 내 인접한 두 요소를 비교하는 과정을 반복하여 제일 큰 요소를 맨 끝으로 이동시키는 정렬 방식이다.

시간복잡도는 O(N**2)로 효율적인 정렬 방식은 아니다.

 

 

 

아래의 배열을 버블 정렬을 이용해 오름차순으로 나타내보자. 지금부터 인덱스는 i로 표현하겠다.

 

 

먼저, i = 0과 i = 1의 요소를 비교한다. 더 큰 수가 왼쪽에 있으므로 서로 위치를 바꿔준다. 

 

 

i = 1과 i = 2를 비교한다. 더 큰 수가 오른쪽에 있으므로 다음으로 넘어간다.

 

 

i = 2와 i = 3을 비교한다. 더 큰 수가 왼쪽에 있으므로 서로 위치를 바꿔준다.

 

 

i = 3과 i = 4를 비교한다. 마찬가지로 더 큰 수가 왼쪽에 있으므로 서로 위치를 바꿔준다.

 

 

(len(array) - 1) 번의 시행을 통해 가장 큰 요소인 5가 제일 오른쪽에 위치하게 되었다.

 

 

5는 그대로 고정해두고, 나머지 요소들에 대한 정렬을 다시 실행한다.

 

 

4가 고정되었다. 사실 이미 오름차순으로 정렬되었지만, 컴퓨터는 이 사실을 알지 못하므로 마저 실행시켜준다.

 

 

버블 정렬이 완료되었다!

 

 

 

버블 정렬을 파이썬로 구현하면 아래와 같다.

def BubbleSort(lst):
	N = len(lst)
	for i in range(N-1):
		for j in range(N-1-i):
			if lst[j] > lst[j+1]:
				lst[j], lst[j+1] = lst[j+1], lst[j]

왼쪽 요소부터 고정시키고 싶다면 아래와 같이 구현할 수도 있다.

def BubbleSort2(lst):
    N = len(lst)
    for i in range(N-1):
		for j in range(N-1, i, -1):
			if lst[j] < lst[j-1]:
				lst[j], lst[j-1] = lst[j-1], lst[j]