거품 정렬

정의

서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘

 

동작 과정

• 1회전에 첫 번째 원소와 두 번째 원소, 두 번째 원소와 세 번째 원소.. n-1번째 원소와 n번째 원소를 비교하여 조건에 맞지 않으면 서로 교환한다.

• 1회전 수행시 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

 

Python 코드

def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1):
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

 

Java 코드

void bubbleSort(int[] arr) {
    int temp = 0;
	for(int i = 0; i < arr.length; i++) {
		for(int j= 1 ; j < arr.length-i; j++) {
			if(arr[j-1] > arr[j]) {
				temp = arr[j-1];
				arr[j-1] = arr[j];
				arr[j] = temp;
			}
		}
	}
	System.out.println(Arrays.toString(arr));
}

 

동작 방식(GIF)

 

시간 복잡도

• (n-1) + (n-2) + (n-3) + …. + 2 + 1 = n(n-1)/2이므로, O(n²)이다.

• 최선, 최악, 평균 모두 시간복잡도가 O(n²)로 동일하다.

 

공간 복잡도

• 별도의 추가 공간을 사용하지 않고 주어진 배열 안에서만 교환하므로 O(1)이다.

 

장점

• 구현이 매우 간단하고, 직관적이다.

• 메모리가 추가로 필요하지않고 공간복잡도가 작다

• 안정된 정렬이다.

단점

• 시간복잡도가 O(n²)로 비효율적이고 오래걸린다.

• 모든 요소와 교환이 되어 연산이 많이 일어나므로 비효율적이다.