[알고리즘] 버블 정렬(bubble sort)

yujamint·2022년 7월 15일

Java ps 알고리즘

PS

목록 보기

4/9

버블 정렬(Bubble Sort)

버블 정렬은 선택 정렬(selection sort)와 유사한 알고리즘으로 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.

정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

정렬 과정

오름차순을 기준으로 정렬한다
원소가 n개 있다고 가정

버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째 자료와 네 번째 자료를, ..., n-1 번째 자료와 n번째 자료를 비교하여 둘 중에 큰 수를 뒤로 보내며 정렬한다.
1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에는 맨 뒤 원소를 제외하고 정렬한다. 2회전을 수행하고 나면 뒤에서 두 번째 원소까지 정렬에서 제외한다. 이렇게 정렬을 1회전 수행할 때마다 제외되는 원소가 하나씩 증가한다. 즉, n회전을 수행하면 뒤에서부터 n개의 원소를 제외하고 정렬을 하는 것이다.

버블 정렬 Java 코드

void BubbleSort() {
	int[] arr = new int[] {13, 5, 11, 7, 23, 15};
    for (int i = arr.length-1; i > 0; i--){
    	for (int j=0; j < i; j++) {
        	if(arr[j] > arr[j+1]) {
            	int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

i는 비교횟수를 의미한다. 1회전엔 (n-1)회 비교하고, 2회전엔 원소 1개를 제외함으로써 (n-2)회 비교한다. 이렇게 1회전마다 비교횟수를 하나씩 줄여간다.
j는 현재 원소를 가리킨다. j를 한 칸씩 옮겨가며 j번 원소와 (j+1)번 원소의 대소를, 즉 인접 원소의 대소를 비교한다.

1회전 : 비교 5회
13과 5를 비교한다. 13이 더 크므로 교환한다.
: 5 13 11 7 23 15
13과 11을 비교한다. 13이 더 크므로 교환한다.
: 5 11 13 7 23 15
13과 7을 비교한다. 13이 더 크므로 교환한다.
: 5 11 7 13 23 15
13과 23을 비교한다. 23이 더 크므로 교환하지 않는다.
: 5 11 7 13 23 15
23과 15를 비교한다. 23이 더 크므로 교환
: 5 11 7 13 15 23
-> 1회전이 끝나며 제일 큰 원소인 23이 맨 뒤로 오게 되었다. 이제 23은 정렬하지 않아도 되므로 2회전에서는 제외한다.
2회전 : 비교 4회
5와 11을 비교한다. 11이 더 크므로 교환하지 않는다.
: 5 11 7 13 15 23
11과 7을 비교한다. 11이 더 크므로 교환한다.
: 5 7 11 13 15 23
11과 13을 비교한다. 13이 더 크므로 교환하지 않는다.
: 5 7 11 13 15 23
13과 15를 비교한다. 15가 더 크므로 교환하지 않는다.
: 5 7 11 13 15 23
-> 2회전이 끝나며 두 번째로 큰 원소인 15가 (n-2)번째 인덱스로 가게 되었다. 3회전에서는 제외한다.
3회전 : 비교 3회
5와 7을 비교한다. 7이 더 크므로 교환하지 않는다.
: 5 7 11 13 15 23
7과 11을 비교한다. 11이 더 크므로 교환하지 않는다.
: 5 7 11 13 15 23
11과 13을 비교한다. 13이 더 크므로 교환하지 않는다.
: 5 7 11 13 15 23
-> 3회전이 끝나며 세 번째로 큰 원소인 13이 (n-3)번째 인덱스에 위치한다. 4회전에서는 제외한다.
4회전 : 비교 2회
5와 7을 비교한다. 7이 더 크므로 교환하지 않는다.
: 5 7 11 13 15 23
7과 11을 비교한다. 11이 더 크므로 교환하지 않는다.
: 5 7 11 13 15 23
-> 4회전이 끝나며 네 번째로 큰 원소인 11이 (n-4)번째 인덱스에 위치한다. 5회전에서는 제외한다.
5회전 : 비교 1회
5와 7을 비교한다. 7이 더 크므로 교환하지 않는다.
: 5 7 11 13 15 23
-> 모든 정렬이 끝나며 오름차순 정렬 완료

시간복잡도

1회전에서의 시간복잡도 : 1 ~ (n-1) => n-1
2회전에서의 시간복잡도 : 1 ~ (n-2) => n-2
...
(n-2)회전에서의 시간복잡도 : 1 ~ 2 => 2
(n-1)회전에서의 시간복잡도 : 1 => 1

(n-1) + (n-2) + (n-3) + ... + 1 = n*(n-1)/2
= n*n
= O(n*n)

n개의 자료가 들어있는 배열을 정렬하는 데에 걸리는 시간은 O(n^2)이다. 최선,평균,최악의 경우 모두 시간복잡도가 O(n^2)으로 동일하다.