버블 정렬(Bubble Sorting)

Seongmin·2023년 5월 22일

원소의 이동이 거품이 수면으로 올라오는 듯한 모습

알고리즘

기본적으로 배열의 두 수를 선택한 뒤,

1-1. 그 수가 정렬되었다면 pass
1-2. 그렇지 않다면 두 수를 바꾸는 방식

시간복잡도 : $O(n^2)$

설명

다음과 같은 배열을 오름차순으로 배열하려고 한다.
int[] arr = {6, 1, 9, 2, 4, 7, 3};
1. 처음부터 맨 끝까지를 범위로 잡고, 앞에서부터 두 원소씩 비교해가며 위치를 옮긴다.
2. 처음부터 맨 끝에서 두번째 까지를 범위로 잡고, 앞에서부터 두 원소씩 비교해가며 위치를 옮긴다.
3. 이를 반복한다.

I. i = 6

j = 0, 1 > 6이므로 두 수를 바꾼다. → [1, 6, 9, 2, 4, 7, 3]

j = 1, 6 < 9이므로 pass

j = 2, 2 > 9이므로 두 수를 바꾼다. → [1, 6, 2, 9, 4, 7, 3]

j = 3, 4 > 9이므로 두 수를 바꾼다. → [1, 6, 2, 4, 9, 7, 3]

j = 4, 7 > 9이므로 두 수를 바꾼다. → [1, 6, 2, 4, 7, 9, 3]

j = 5, 3 > 9이므로 두 수를 바꾼다. → [1, 6, 2, 4, 7, 3, 9]

I. i = 5

j = 0, 1 < 6이므로 pass

j = 1, 2 > 6이므로 두 수를 바꾼다. → [1, 2, 6, 4, 7, 3, 9]

j = 2, 4 > 6이므로 두 수를 바꾼다. → [1, 2, 4, 6, 7, 3, 9]

j = 3, 6 < 7이므로 pass

j = 4, 3 > 7이므로 두 수를 바꾼다. → [1, 2, 4, 6, 3, 7, 9]

I. i = 4

j = 0, 1 < 2이므로 pass

j = 1, 2 < 4이므로 pass

j = 2, 4 < 6이므로 pass

j = 3, 3 > 6이므로 두 수를 바꾼다. → [1, 2, 4, 3, 6, 7, 9]

I. i = 3

j = 0, 1 < 2이므로 pass

j = 1, 2 < 4이므로 pass

j = 2, 3 > 4이므로 두 수를 바꾼다. → [1, 2, 3, 4, 6, 7, 9]

I. i = 2

j = 0, 1 < 2이므로 pass

j = 1, 2 < 3이므로 pass

I. i = 1

j = 0, 1 < 2이므로 pass

코드 구현

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {1, 6, 9, 2, 4, 7, 3};
        for(int i = arr.length - 1; i > 0 ; i--){
            for(int j = 0; j < i; j++){
                if(arr[j] > arr[j + 1]){  // ··· (1)
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j+1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}