[정렬 알고리즘] 버블 정렬(Bubble Sort)

버블 정렬 과정

버블 정렬이란?

버블 정렬은 원소를 비교하는 과정에서 연탄 나르기와 비슷하다. 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하는 정렬 알고리즘이다. 시간 복잡도가 O(n²)로 상당히 느리지만, 소스코드가 직관적이고 구현이 매우 간단하다는 장점이 있다.

 

버블 정렬 장점과 단점

버블 정렬 장점	구현이 매우 간단하고, 소스코드가 직관적이다.
	정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않다. ➡ 제자리 정렬(in-place sorting)
버블 정렬 단점	시간복잡도가 최악, 최선, 평균 모두 O(n²)으로, 굉장히 비효율적이다.
	정렬 돼있지 않은 원소가 정렬 됐을 때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 된다.

 

시간 복잡도

알고리즘	Best	Avg	Worst	Run-time(정수 60,000개) 단위: sec
삽입정렬	O(n)	O(n²)	O(n²)	7.438
선택정렬	O(n²)	O(n²)	O(n²)	10.842
버블정렬	O(n²)	O(n²)	O(n²)	22.894
셸 정렬	O(n)	O(n¹·⁵)	O(n²)	0.056
퀵 정렬	O(nlogn)	O(nlogn)	O(n²)	0.014
힙 정렬	O(nlogn)	O(nlogn)	O(nlogn)	0.034
병합 정렬	O(nlogn)	O(nlogn)	O(nlogn)	0.026

 

버블 정렬 알고리즘 구현

//버블 정렬은 매 반복마다 가장 큰 값을 배열의 끝으로 이동시킨다.
//첫 번째 반복에서는 가장 큰 값이 배열의 마지막 자리에 놓이게 되고, 그 후 반복마다 정렬되지 않은 영역이 줄어든다.

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

1. 맨 앞부터 시작하여, 인접한 값과 비교하여 큰 값은 배열의 뒤로, 작은 값은 배열의 앞으로 보낸다.
2. 해당 과정을 거치면 맨 뒤에는 가장 큰 값이 위치할 것이다.
3. 뒤쪽의 정렬된 값을 제외하고 나머지에 대해서 같은 과정을 수행하여 전체 배열에 대한 정렬을 수행한다.

 

참고자료

[1] 위키백과 - 버블 정렬

[2] Heee's Development Blog - [알고리즘] 버블 정렬(bubble sort)이란

[3] ShootForTheMoon - [기술면접] 알고리즘 - 1/2 (6개 정렬 알고리즘)

[4] 데굴데굴 개발자의 기록 - [알고리즘/JAVA] 정렬 알고리즘 : 선택, 삽입, 버블, 병합, 퀵 정렬