정렬 - Bubble Sort

두 개의 인접한 원소(값)을 비교하여 정렬하는 것

버블 정렬에 대해 알아보기 위해 배열을 오름차순으로 나타내는 것을 기준으로 한다.

간단하게 말하면, 두개씩 값을 비교하고, 조건에 맞게 swap하는 것이다.

 

1. array[0]에서부터 비교(첫번째 cycle)

int[] array = { 1, 5, 9, 3, 7, 1, 0}; 인 배열 array을 오름차순으로 정렬하는 것을 예로 들어 설명하도록 한다.

먼저, array[0]과 array[1]을 비교했을 때, array[0] < array[1]이므로 swap할 필요가 없다.

같은 방식으로, array[1]와 array[2] 또한 swap할 필요가 없다.

이때, array[2] > array[3]이므로 두 원소를 swap해야 한다.

같은 방식으로 진행한 결과는 다음과 같다.

첫 번째 cycle 결과 배열 array는 { 1, 5, 3, 7, 1, 0, 9 }가 되었다.

 

2. 두번째 사이클

3. 세번째 사이클

4. 네번째 사이클

5. 다섯번째 사이클

6. 여섯번째 사이클

최종적으로 버블 정렬을 통해 오름차순 정렬을 한 결과는 {0, 1, 1, 3, 5, 7, 9}이다.

 

이제 코드를 작성하여 결과를 비교해보자.

import java.util.Arrays;
 
public class test {
 
    public static void main(String[] args) {
        // 오름차순
        int[] array = { 1, 5, 3, 9, 7, 1, 0 };
        int tmp; // swap을 위한 변수 선언
        // cycle은 (배열의 크기-1)만큼 진행된다.
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    tmp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = tmp;
                }
            }
        }
        System.out.println(Arrays.toString(array));
 
    }
 
}
 

동일한 결과가 나타난다. 

 

내림차순으로 정렬하는 경우는 오름차순 정렬과 같은 논의이므로 부등호의 방향만 달리하면 된다.

import java.util.Arrays;
 
public class test {
 
    public static void main(String[] args) {
        // 내림차순
        int[] array = { 1, 5, 3, 9, 7, 1, 0 };
        int tmp; // swap을 위한 변수 선언
        // cycle은 (배열의 크기-1)만큼 진행된다.
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] < array[j + 1]) {
                    tmp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = tmp;
                }
            }
        }
        System.out.println(Arrays.toString(array));
 
    }
 
}
 

결과는 { 9, 7, 5, 3, 1, 1, 0}.