버블정렬(bubble sort)

이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하는 정렬

원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

1. 맨 끝 두 개의 요소를 비교한다. 저울로 비교한다고 생각. (맨 앞에서 시작한다면 반대로 생각해서 진행)
2. 오른쪽 숫자가 작으면 왼쪽과 교환한다.
3. 비교를 완료했으면 저울을 한칸 왼쪽으로 이동한다.
4. 동일한 방법으로 숫자를 비교한다.
5. 위의 방법을 저울이 왼쪽 끝에 도착할 때 까지 반복한다.
6. 저울이 왼쪽 끝에 도착했다면 가장 작은 숫자가 왼쪽 끝에 이동된다.
7. 왼쪽 끝의 숫자는 정렬을 끝낸 것으로 간주하고 저울을 다시 오른쪽 끝으로 이동하여 모든 숫자가 정렬될 때까지 1~6번을 반복한다.

버블정렬 - 예시

• 정렬되지 않은 위의 항목들을 이용하여 선택정렬을 한다.
  

• 오른쪽 맨 끝 저울을 두고 좌우 숫자를 비교한다.
• 5 > 4 이므로 둘의 순서를 변경한다.
  

• 비교를 완료했으면 저울을 한칸 옆으로(왼쪽) 이동하여 동일한 방법으로 숫자를 비교한다.
• 7 > 4 이므로 둘의 순서를 변경한다.
  

• 비교를 완료했으면 저울을 한칸 옆으로(왼쪽) 이동하여 동일한 방법으로 숫자를 비교한다.
• 6 > 4 이므로 둘의 순서를 변경한다.
  

• 비교를 완료했으면 저울을 한칸 옆으로(왼쪽) 이동하여 동일한 방법으로 숫자를 비교한다.
• 이번에는 2 < 4 이므로 순서를 변경하지 않는다.(회색으로 표시)

• 동일한 작업을 저울이 왼쪽 끝에 도착할 때 까지 반복한다.
  

• 저울이 왼쪽 끝에 도착했고, 위의 작업을 거쳐 가장 작은 숫자가 왼쪽 끝에 이동(정렬)됐다.
  

• 다시 저울을 오른쪽 끝으로 옮겨 모든 숫자가 정렬될 때 까지 위의 작업들을 반복한다.
  

애니메이션

버블정렬 전체 과정 애니메이션이다.

버블정렬 - Java 코드

public class BubbleSortTest {

    // 자리이동
    static void swap(int[] arr, int idx1, int idx2) {
        int tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }

    static void bubbleSort(int[] arr) {
        // 수행하는 패스의 횟수는 (배열길이 - 1)회. 마지막 요소는 이미 끝에 놓이기 때문이다.
        for(int i = 0; i < arr.length - 1; i++) {
            // 끝에서 부터 비교하므로 j를 배열의 마지막으로 지정
            // arr[j-1]과 arr[j]를 비교한다.
            for(int j= arr.length - 1 ; j > i; j--) {
                if(arr[j - 1] > arr[j]) {
                    // 자리이동
                    swap(arr, j -1, j);
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 2, 6, 7 , 5, 4};

        // 버블정렬
        bubbleSort(arr);

        // 결과 출력
        System.out.println(Arrays.toString(arr));

    }
}

버블정렬 특징

• 장점
  • 구현이 매우 쉬워서 코드 자체가 직관적이다.
• 단점
  • 최선이든 최악이든 시간복잡도 O(n2) 로 인하여 정렬 시간이 오래 걸린다.
    • 따라서, 효율적인 정렬방법으로 사용되지 않음.
  • 하나의 요소가 끝에서 끝으로 이동하기 위해서 배열의 모든 다른 요소들과 교환되어야 한다.
  • 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 발생한다.

References

• 버블정렬-위키백과
• https://gmlwjd9405.github.io/2017/10/01/basic-concepts-of-development-algorithm.html
• https://yabmoons.tistory.com/250
• 보요 시바타, 『자료구조와 함께 배우는 알고리즘 입문』, 이지스퍼블리싱(2018)
• 모든 이미지는 직접 그림