[정렬] 버블정렬(Bubble sort)

 

버블정렬 (Bubble sort)

 

인접한 두 값을 비교하여 자리 교환하는 방식이다.

첫 번째 값부터 반복적으로 비교하여 한 바퀴가 끝나고 나면 마지막 값은 가장 큰 값이 된다.

선택정렬 대비 swap이 많이 이루어지기 때문에 자료가 역순으로 정렬되어 있을 경우 성능이 좋지 않다.

반대로 정렬이 어느정도 이루어져 있는 경우 성능이 좋다.

---

 

버블정렬 수행과정

 

배열 {23, 4 ,7, 12, 2, 1} 버블정렬 과정

1. 23과 4 비교, 23이 더 크므로 swap

{4, 23, 7, 12, 2, 1}

2. 23과 7 비교, 23이 더 크므로 swap

{4, 7, 23 ,12, 2, 1}

3. 23과 12 비교, 23이 더 크므로 swap

{4, 7, 12, 23, 2, 1}

4. 23과 2 비교, 23이 더 크므로 swap

{4, 7, 12, 2, 23, 1}

5. 23과 1 비교, 23이 더 크므로 swap

{4, 7, 12, 2, 1, 23}

6. 이 과정을 반복하게 되면 큰 값들이 끝자리 부터 정리되게 된다.

---

 

• 예제 코드

public class BubbleSort {
    public static void bubbleSort(int arr[], int last) {
        if (last > 0) {
            for (int i = 0; i < last; i++) {
                if (arr[i] > arr[i+1]) {
                    swap(arr, i, i + 1);
                }
            }
            bublleSort(arr, last - 1);
        }
    }

    public static void swap(int arr[], int index1, int index2) {

        int tmp;
        tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }

    public static void printArray(int arr[]) {
        for (int data : arr) {
            System.out.print(data + ", ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int arr[] = { 23, 4, 7, 12, 2, 1 };
        printArray(arr);
        bubbleSort(arr, arr.length - 1);
        printArray(arr);

    }
 }

결과 : 23, 4, 7, 12, 2, 1

        1, 2, 4, 7, 12, 23