버블정렬

버블정렬

• 거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

6 2 7 8 1

• 6보다 2이 작기 때문에 교환

2 6 7 8 1

• 6보다 7이 크기 때문에 교환 하지 않는다.

2 6 7 8 1

• 7보다 8이 크기 때문에 교환 하지 않는다.

2 6 7 8 1

• 8보다 1이 작기 때문에 교환

2 6 7 1 8

• 다시 처음으로 돌아가 반복 한다.

private static void bubbleSort(int[] arr){
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

조금 나은 버블정렬

버블 정렬은 각각 한번씩 i랑 i+1 을 비교하므로 만약 한번도 교환이 일어 나지 않았다면 정렬이 된 상태다. 그걸 이용해서 조금 더 나은 버블정렬을 구현할 수 있다.

private static void bubbleSort(int[] arr){
    for (int i = 0; i < arr.length; i++) {
        boolean checked = false;
        for (int j = 0; j < arr.length - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                checked = true;
            }
        }
        if(!checked){
            break;
        }
    }
}