버블 정렬(Bubble Sort)

주의 ! 이 내용은 글쓴이가 공부하기 위해 작성한 글로서 부정확할 수 있습니다. (반박시 니 말 다 맞음)

 

버블 정렬(또는 거품 정렬)은 인접한 두 원소를 검사하여 정렬하는 방법이다.

시간 복잡도가 O(N²)으로 상당히 느리지만 그만큼 코드 구현이 쉽다.

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

양방향으로 번갈아 수행하면 칵테일 정렬(?)이 된다고 한다.

 

무작위 배열수의 거품 정렬 예(나무위키)

아이디어

버블 정렬은 간단하다. 인접한 두 개의 원소를 비교하기만 하면된다. 한 턴이 지나면 맨 오른쪽은 가장 큰 값이 자리하게 된다. 예를 들자면

1 턴  97 64 34 59 72   첫번째와 두번째 비교 64 97 34 59 72   두번째와 세번째 비교 64 34 97 59 72   세번째와 네번째 비교 64 34 59 97 72   네번째와 다섯번째 비교 2 턴 64 34 59 72 97  첫번째와 두번째 비교 34 64 59 72 97  두번째와 세번째 비교 34 59 64 72 97  세번째와 네번째 비교(패스) 34 59 64 72 97  네번째와 다섯번째 비교(패스) -> 끝

코드구현(자바)

간단한 2중 for문으로 구현 가능한데 한 턴이 지나면 맨 오른쪽에는 가장 큰 값이 배치되므로 턴이 지날 때마다 arr.length 에 i 를 빼주면서 비교한다.

int tmp;
for (int i = 0; i < arr.length - 1; i++) {
    for (int j = 1; j < arr.length - i; j++) {

첫번째 원소(arr[j-1])와 두번째 원소(arr[j])를 비교하면서 만약 첫번째 원소가 두번째 원소보다 크면 두 수의 위치를 바꿔준다.

        if(arr[j] < arr[j-1]) {
            tmp = arr[j-1];
            arr[j-1] = arr[j];
            arr[j] = tmp;
        }
    }
}
return arr;

전체코드

package bubbleSort;

public class BubbleSort {
    public static int[] bubbleSort(int[] arr) {
        int tmp;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 1; j < arr.length - i; j++) {
                if(arr[j] < arr[j-1]) {
                    tmp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
        return arr;
    }
}

실행

package bubbleSort;

import java.util.Arrays;

public class BubbleSortTest {
    public static void main(String[] args) {
        int [] arr = {97, 64, 34, 59, 72};
        System.out.println(Arrays.toString(BubbleSort.bubbleSort(arr)));
    }
}