[알고리즘은 처음이라] Bubble Sort(거품 정렬)

 

면접 준비 겸 코테 준비 겸 정렬부터 하나하나 정리 해보려고 한다!

 

🌈요약

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

시간복잡도
O(n^2)
- Bubble Sort는 정렬 유무 관계 없이 항상 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 시간복잡도가 모두 O(n^2)으로 동일

공간복잡도
O(n)
- 주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되는 제자리 정렬

 

 

---

Bubble Sort (거품 정렬)이란?

Selection Sort와 유사한 알고리즘

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

 

 

진행 과정(오름차순)

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

 

 

구현(Java)

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.
            	temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

 

1. 한 번의 회전이 끝난 후 배열의 마지막 위치에 가장 큰 원소가 위치하기 때문에 i를 하나씩 증가시켜서 한 번의 회전이 끝난 후 정렬에서 제외될 원소 갯수를 증가 시켜준다. 

 

2. 원소를 비교하는 for문이다. j는 현재 원소를, j-1은 이전 원소를 가리키기 때문에 j는 1부터 시작한다.

 

3. 현재 가르키고 있는 두 원소의 대소를 비교한다. 현재 코드는 오름차순 정렬이기 때문에 현재 원소보다 이전 원소가 크면 두 원소 자리를 서로 교환한다.

 

 

시간복잡도

(n-1) + (n-2) + (n-3) + ... 2 + 1 >> n(n-1)/2 이기 때문에 O(n^2)

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

 

 

 

공간복잡도

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

 

 

장점

• 구현이 간단하고 소스코드가 직관적이다.
• 정렬하고자하는 배열 안에서 교환하는 방식이기 때문에 다른 메모리 공간을 필요로 하지 않는다
  >> 제자리 정렬(in - place sorting)
• 안정 정렬(stable sort)이다.

 

단점

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

 

---

참고자료

거품 정렬

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