Sort(2) - Bubble Sort (버블정렬)

Bubble Sort (버블정렬)

: (오름차순 기준) 바로 옆에 있는 데이터와 비교해서 작은 값을 앞으로 보낸다.

Selection Sort때와 마찬가지의 예를 들어보자.

7, 1, 5, 4, 2 이렇게 다섯 가지의 숫자를 오름차순으로 정렬한다고 해보자.

7 1 5 4 2

첫 번째 원소인 7과 다음 원소인 1을 비교해서 더 작은 값인 1을 앞으로 보낸다.

7 1 5 4 2

1 7 5 4 2

이제 두 번째 원소인 7과 다음 원소인 5를 비교해서 더 작은 값인 5를 앞으로 보낸다.

1 7 5 4 2

1 5 7 4 2

위 작업을 데이터의 끝까지 반복하면 아래와 같은 형태가 된다.

1 5 4 2 7

첫 번째 loop가 끝났으니, 두 번째 원소부터 다시 다음 원소와 비교를 시작한다.

1 5 4 2 7

이렇게 마지막 loop까지 돌고 나면 정렬이 완료된다.

1 2 4 5 7

코드

Bubble_Sort(int arr[], int n) {
	for(int i = 0; i < n - 1; i++) {
    		for(int j = i + 1; j < (n - 1) - i; j++) {
            		//arr[j]와 arr[j + 1]를 비교
                    	//arr[j]가 크기가 더 크다면 둘의 위치를 변경
            	}
    	}
}

시간 복잡도

데이터가 N개일 때 이중for문을 통해 연산수행이 N번 + N-1번 + ... + 1번 수행되므로 총 N(N+1)/2번의 비교연산이 수행된다. 따라서 시간복잡도 O는 O(N^2) 를 따르게 된다. 하지만 계속해서 비교연산을 수행한다는 점에서 같은 O(N^2)인 선택정렬보다 더 느린 정렬이라고 볼 수 있다.