Algorithm - 거품 정렬 (Bubble Sort)

코난·2024년 2월 25일

CS 면접 정리

목록 보기

32/67

거품 정렬이란?

거품 정렬은 인접한 두 수를 비교하여 더 큰 수를 뒤로 보내는 간단한 정렬 알고리즘이다. 큰 그림으로 보면 뒤에서부터 앞으로 정렬해나가는 구조를 가지고 있다. 각 원소의 이동이 거품 방울이 수면으로 올라오는 듯한 모습을 보이기 때문에 거품 정렬이라는 이름을 가지게 되었다고 한다.

거품 정렬의 과정

마지막 원소를 만날때까지 현재 원소와 다음 원소를 비교한다.
현재 원소가 더 큰 경우 두 원소를 서로 교환한다. (swap)
값이 정해진 마지막 원소(가장 큰 값)를 제외하고 위의 과정을 반복한다.

거품 정렬의 특징

데이터를 비교하면서 찾기 때문에 비교 정렬임
정렬의 대상이 되는 데이터 외에 추가 데이터 공간을 필요로 하지 않기 때문에 제자리 정렬임
앞에서부터 차례대로 비교하기 때문에 안정 정렬임

자바 구현 코드

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

제외될 원소를 개수를 의미하며 배열의 끝쪽에 차롈대로 가장 큰 원소가 위치하고 위치가 고정되어야 하기 때문에 계속하여 하나씩 증가시켜줌.
원소를 비교할 index를 뽑을 반복문으로 j는 현재 원소, j - 1은 이전 원소를 가리키게 됨.
현재 가리키는 두 원소의 대소를 비교하고 현재 원소보다 이전 원소가 크다면 swap을 수행해줌.

시간 복잡도 & 공간 복잡도

버블 정렬은 정렬이 되어 있던 안되어있던 2개의 원소를 계속하여 비교하기에 최선, 평균, 최악의 경우 모두 시간 복잡도는 O(n^2)이다. (비교 연산의 횟수는 n(n - 1) / 2이다.)
주어진 배열 안에서 교환을 통해 정렬이 수행되고 추가적인 공간은 필요하지 않기 때문에 공간 복잡도는 O(n)이다.