버블 정렬(Bubble Sort)

  거품 정렬이라고도 불리는 버블 정렬에 대해서 알아보자.

1. 정의 👟

버블 정렬

  버블 정렬은 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.

 

2. 동작 방식 👞

  N개의 원소가 있다고 하자.
  첫 번째 원소와 두 번째 원소를 비교하여 만약 첫 번째 원소가 더 크다면 둘의 자리를 바꿔준다. 그리고 두 번째 원소와 세 번째 원소를 비교하여 만약 두 번째 원소가 더 크다면 둘의 자리를 바꿔준다. 이러한 동작을 (마지막 - 1) 번째의 원소와 마지막 원소를 비교할 때까지 수행한다.
  이것이 1회전 수행한 것이다. 이렇게 되면 마지막에 위치한 원소가 가장 큰 원소가 된다. 2회전을 수행할 때 마지막 원소를 제외한 나머지들을 정렬해 준다. (N - 1) 회전까지 수행하면 정렬이 마무리된다.
  위의 방식은 오름차순으로 정렬을 하고 있다. 만약 대소를 비교하여 뒤의 원소가 더 클 때 앞의 원소와 자리를 바꾼다면 내림차순으로 정렬을 할 수 있다.

 

3. 구현(JAVA) 🥾

static void bubbleSort(int[] arr) {
    int temp = 0;
    // (원소의 개수 - 1)번 반복
    for(int i = 0; i < arr.length - 1; 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;
            }
        }
    }
}

 

4. 시간복잡도 & 공간복잡도 👢

1. 시간복잡도

  위에서 살펴봤듯이 총 (N - 1)번 회전하고, i번째 회전에서 (N - i)의 연산을 수행한다. 그러면, 아래에 해당하는 수만큼 연산을 수행한다.

(N - 1) + (N - 2) + (N - 3) + ... + 2 + 1 = N * (N -1) / 2

  따라서, 시간복잡도는 O(N^2)이다.
  정렬이 되어있던 안되어 있던 항상 비교를 수행하므로 최선, 평균, 최악의 상황에서 모두 O(N^2)의 시간복잡도를 가진다.

	최선(BEST)	평균(AVERAGE)	최악(WORST)
시간복잡도	O(N^2)	O(N^2)	O(N^2)

2. 공간복잡도

  공간복잡도의 경우 추가적인 배열을 만들지 않고 해당 배열에서 교환이 이루어지므로 O(N)이다.

 

5. 장점 & 단점 🥿

1. 장점

• 코드가 매우 단순한다.
• 다른 메모리 공간을 필요로 하지 않는다.

2. 단점

• 시간복잡도가 O(N^2)이므로 상당히 비효율적이다.
• 정렬이 되어있더라도 비교 연산을 수행한다.

 

해당 글은 Gyoogle님의 거품 정렬(Bubble Sort)을 참고하였습니다.