[알고리즘]정렬-거품정렬(Bubble Sort)

거품정렬 : 선택정렬과 유사한 알고리즘으로, 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘

과정(오름차순 기준)

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

 

 

Java Code - 오름차순 기준

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]) {    
            
                // swap(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^2) 로 나타낼 수 있다. 정렬이 돼있던 안돼있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 O(n^2) 으로 동일합니다. 

공간복잡도 : 주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)입니다.

🔈 시간복잡도, 공간복잡도가 뭔지 모르겠다면 글 확인하기!

2020/02/11 - [기술면접] - [알고리즘] 계산복잡도 - 시간복잡도, 공간복잡도

[알고리즘] 계산복잡도 - 시간복잡도, 공간복잡도

 

장점과 단점

장점

• 구현이 매우 간단하고 소스코드가 직관적이다.
• 정렬하고자 하는 배열 안에서 교환하는 방식으로, 다른 메모리를 필요로 하지 않는다. 즉, 제자리 정렬(in-place sorting)이다.
• 안정 정렬(Stable Sort)이다.

단점

• 정렬 되어있지 않은 원소가 정렬 됐을 때의 자리로 가기 위하여 교환 연산이 많이 일어나게 된다.

 

 

자료출처 및 참고 사이트

https://github.com/GimunLee/tech-refrigerator/blob/master/Algorithm/%EA%B1%B0%ED%92%88%20%EC%A0%95%EB%A0%AC%20(Bubble%20Sort).md#%EA%B1%B0%ED%92%88-%EC%A0%95%EB%A0%AC-bubble-sort

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

https://jinhyy.tistory.com/9