거품 정렬(Bubble Sort)

개념

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

 

과정

1. 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … , (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다.
2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

 

구현(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));
}

 

시간복잡도

(n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2이므로, O(n^2) 이다.

또한, Bubble Sort는 정렬 여부와 무관하게 인접한 두 원소를 비교하기 때문에 최선, 평균, 최악의 시간복잡도가 O(n^2) 으로 동일하다.

 

 

 

 

 

 

 

 

 

 

---

 

참고 

https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html