버블 정렬 (Bubble Sort)

 

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

가장 큰 값을 배열의 맨 끝에 이동시키면서 정렬하고자 하는 원소의 개수 만큼을 두 번 반복하게 된다.

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

 

구현

 

	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;
	}
	}
	}
	}

view raw BubbleSort.cpp hosted with ❤ by GitHub

 

 

 

시간 복잡도

 

(n - 1) + (n - 2) + ... + 2 + 1 = n(n-1)/2이므로 O(n^2)

 

정렬이 되어있든지 안되어있든지 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간 복잡도가 O(n^2)으로 동일하다.

 

 

공간 복잡도

 

주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되므로 O(n)

 

 

장점

• 구현이 매우 간단하고 소스코드가 직관적이다.
• 추가적인 메모리 소비가 적다.
• in-place sort, stable sort

 

단점

 

• 시간 복잡도가 최선, 평균, 최악의 경우 모두 O(n^2)이므로 굉장히 비효율적이다.
• 정렬되어 있지 않은 원소가 정렬되었을 때의 자리로 가기 위해서 교환 연산(swap)이 많이 일어나게 된다.

 

In-place Sort (제자리 정렬)
추가적인 메모리 공간을 많이 필요로 하지 않는 혹은 전혀 필요하지 않는 알고리즘

Stable Sort (안정 정렬)
중복된 키를 순서대로 정렬하는 정렬 알고리즘

 

 

 

Reference

거품 정렬(Bubble Sort) | 👨🏻‍💻 Tech Interview