버블정렬

atesi·2022년 6월 3일

algorithm

목록 보기

3/5

Charpter. 0

앞에서 정리한 빅 오 표기법은 알고리즘을 객관적으로 측정할 수 있어서 경쟁 알고리즘을 비교할 때 휼륭한 도구가 된다. 이분탐색이 $O(log N)$ 이므로 $O(N)$ 인 선형검색 보다 빠른 알고리즘이라할 수 있다. 내가 만든 알고리즘을 더 빠른 빅 오 카테고리에 들어갈 수 있게 최적화 하는 방법을 생각해 봐야한다.

Chatper. 1

1. 버블정렬

정렬되지 않은 배열이 주어졌을 때 어떻게 오름차순으로 정렬할 수 있을까?
기본적인 정렬 알고리즘인 버블 정렬의 단계를 살펴보자.

배열 내에서 연속된 두 항목을 가르킨다. 두 항목을 비교한다.
두 항목의 순서가 바뀌어 있으면 다시말해 왼쪽 값이 오른쪽 값보다 크면 교환(Swap)한다. (순서가 올바르면 아무것도 안한다.)
한 셀씩 오른쪽으로 옮긴다. 1단계와 2단계를 반복한다.
더 이상 교환되지 않을 때 까지 1단계에서 3단계를 반복한다(패스스루=1단계에서 3단계 반복). 더는 교환 하지 않는다는 것은 배열이 정렬된 상태라는 것이다.

2. 예제

배열 [4,2,7,1,3]을 오름차순으로 정렬해보자.

먼저 4와 2를 비교한다.
순서가 맞지 않으니 둘을 교환한다. [2,4,7,1,3]
다음 4와 7을 비교한다. 순서가 올바르니 교환하지 않는다.
이제 7과 1을 비교한다.
순서가 맞지 않으니 둘을 교환한다. [2,4,1,7,3]
7과 3을 비교한다.
순서가 맞지 않으니 둘을 교환한다. [2,4,1,3,7]

이제 7은 배열 내에서 올바른 위치에 있다. 이 알고리즘을 버블 정렬이라 부르는 까닭이 바로 여기에 있다. 각 패스스루마다 정렬되지 않은 값 중 가장 큰 값 '버블'이 올바른 위치로 가게 된다.

첫 번째 패스스루에서 교환을 적어도 한 번 수행 했으니 다음 패스스루를 수행한다.
8. 2와 4를 비교한다. 순서가 올바르니 다음 단계로 넘어간다.
.
.
.
15. 2와 3을 비교한다. 순서가 올바르니 교환할 필요가 없다. [1,2,3,4,7]
세 번째 패스스루에서 교환을 적어도 한 번 수행 했으니 다음 패스스루를 수행한다.
16. 1과 2를 비교한다. 순서가 올바르니 교환하지 않는다.
네 번째 패스스루를 종료한다. 어떤 교환도 하지 않아 배열은 정렬된 상태라고 할 수 있다.

3. 버블정렬 구현

파이썬으로 구현한 버블 정렬이다.

def bubble_sort(list):

	#어떤인덱스까지 아직 정렬되지 않았는지 기록, 배열의 마지막 인덱스로 변수를 초기화 한다.
	unsorted_untill_index = len(list) - 1
    #배열의 정렬 여부를 기록하는 sorted 변수 생성.
    sorted = False
    
    #정렬될 때 까지 실행할 while 루프를 시작.
    #sorted = True 값을 교환하는 즉시 False로 변경하여 어떤 교환도 하지 않아 패스스루를 통과했다면 배열이 정렬된 상태. 
    while not sorted:
    	sorted = True
        #배열의 첫인덱스부터 정렬되지 않은 인덱스까지 for문 수행, 인접 값을 비교하고 교환, 교환하면 sorted를 False로 바꾼다.
    	for i in range(unsorted_untill_index):
        	if list[i] > list[i+1]
            sorted = False
            list[i], list[i+1] = list[i+1], list[i]
         
        #마지막 인덱스는 버블이기 때문에 1을 감소시킨다.
        unsorted_untill_index = unsorted_untill_index - 1

list = [65, 66, 45, 35, 25, 15, 10]
bubble_sort(list)
print(list)

4. 효율성

버블정렬 알고리즘에 포함된 단계는 두종류이다.

비교 : 어느쪽이 더 큰지 두 수를 비교한다.
교환 : 정렬하기 위해 두 수를 비교한다.

예제의 원소는 5개다. 비교의 경우 첫번째 패스스루에서 두수의 비교를 4번 해야한다. 두번째 3번, 세번째 2번, 네번째 1번 따라서 총 10번의 비교다. 원소 N개가 있다면 $(N-1)+(N-2)...+1$ 번의 비교를 수행.

교환의 경우 내림차순(최악의 시나리오)라면 비교할 때 마다 교환을 해야한다. 예제의 경우 10번의 비교를 했으니 교환도 10번 수행해야한다. 만약 원소가 10개가 역순으로 된 배열에서는 45번의 비교와 45번의 교환이 일어나 총 90단계다. 원소가 20개라면 190번의 비교 190번의 교환 380단계. 정확하지 않지만 대략 N의 제곱만큼 늘어남을 알게된다.
버블정렬의 효율성을 $O(N^2)$ 이라 부른다. 이차시간이라고도 한다.