[ Algorithm ] Bubble Sort(버블 정렬)

버블 정렬(Bubble Sort)#

버블 정렬은 가장 간단한 정렬 알고리즘(sorting algorithm) 중 하나이다.¹ 가장 기본적인 정렬 알고리즘이고, 고안해내지 못하더라도, 항상 기억하고는 있어야 하는 정렬중 하나이다.

작동 원리#

버블 정렬은 이웃한 두 요소를 비교하여 올바른 순서로 교환하는 과정을 반복하는 정렬 알고리즘이다. 목록을 한 번 순회할 때마다 가장 큰 값이 맨 위로 이동하게 되는데, 이는 마치 물속에서 큰 기포가 더 빠르게 수면으로 떠오르는 모습과 유사하여 버블 정렬이라는 이름이 붙게 되었다.

버블 정렬은 간단한 아이디어를 구현한 것이다. 오름차순으로 정렬하려는 정수 컬렉션이 있다고 가정하자. 버블 정렬은 두 개의 인접한 요소를 한 번에 고려한다. 이 두 인접 요소가 순서가 잘못되었다면(이 경우, 왼쪽 요소가 오른쪽 요소보다 엄격히 크다면), 버블 정렬은 이들을 교환한다. 그런 다음 다음 쌍의 인접 요소로 진행한다. 버블 정렬의 첫 번째 패스에서는 컬렉션의 모든 인접 요소 세트를 한 번씩 처리하며 필요에 따라 교환을 수행한다. 버블 정렬의 핵심 아이디어는 단일 패스에서 더 이상 교환이 이루어지지 않을 때까지 이 과정을 반복하는 것이며, 이는 리스트가 정렬되었음을 의미한다.

시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)#

평균 수행 시간: $O(N^2)$
최악 수행 시간: $O(N^2)$
메모리(공간 복잡도): $O(1)$
안정성: O

버블 정렬의 실행 시간은 배열이 정렬될 때까지 수행해야 하는 패스 횟수에 전적으로 기반한다. 배열에 n개의 요소가 있다면, 각 패스는 (n-1) 쌍을 고려한다. 최악의 경우, 최소 요소가 리스트의 끝에 있을 때, 리스트의 앞쪽 적절한 위치로 이동시키는 데 (n-1) 패스가 필요하고, 더 이상 교환이 필요 없다는 것을 확인하기 위해 추가로 한 번의 패스가 필요하다.

버블 정렬은 안정적인(stable) 정렬 알고리즘이다. 동일한 요소들의 상대적 순서가 보존되기 때문이다.

전반적으로 버블 정렬은 구현하기 쉽고 안정적이지만, 그 외에는 바람직한 특징이 많지 않다. 대부분의 입력에 대해 상당히 느리며, 따라서 실제로는 거의 사용되지 않는다.

코드#

public class BubbleSort implements Sort{  
    @Override  
    public int[] sort(int[] array) {  
        for(int i = 0; i < array.length - 1; i++) {  
            for(int j = 0; j < array.length - i - 1; j++) {  
                if(array[j] > array[j + 1]) {  
                    int temp = array[j];  
                    array[j] = array[j + 1];  
                    array[j+1] = temp;  
                }  
            }  
        }  
        return array;  
    }  
}

또는 최적화된 버전

public class Solution implements Sort {
   @Override
   public int[] sort(int[] array) {
       boolean hasSwapped = true;
       while (hasSwapped) {
           hasSwapped = false;
           for (int i = 0; i < array.length - 1; i++) {
               if (array[i] > array[i + 1]) {
                   int temp = array[i];
                   array[i] = array[i + 1];
                   array[i + 1] = temp;
                   hasSwapped = true;
               }
           }
       }
       return array;
   }
}