[알고리즘] 9. 버블 정렬

버블 정렬

• {5, 3, 1, 2, 4}의 배열을 버블 정렬을 이용하여 정렬하시오.

문제 분석

• 버블 정렬의 동작 원리 : 1번과 2번을 비교하여, 1번이 크면 2번 자리로 swab

• 5칸의 배열을 정렬하기 위해 필요한 최대 동작 수 : 10번 ( 4 + 3 + 2 + 1 )

• 시간복잡도 = ?

코드 작성 - Sampling, Moduling

package algo;

// 정렬 [1, 2, 3, 5, 4] 버블, 삽입, 선택, 퀵 솔트
public class Bubble02 {
    public static void main(String[] args) {
        // 1. Sampling : 배열을 [7, 5, 3, 1, 2, 4, 6]로 설정
        int[] arr = {7, 5, 3, 1, 2, 4, 6};
        int tmp;
        // 3. Moduling : 반복문 중단을 위한 count 변수
        int count = 0;
        // 3. Moduling : 반복문 중단을 위한 count 비교 변수
        int tmp_count = 0;

        // 2. Hard Coding - 특징 찾기 1 : 5개의 칸을 정렬하려면 최대 4번의 반복이 필요 (마지막 칸은 알아서 정렬되기 때문에 계산할 필요 없음)
        // 2. Hard Coding - 특징 찾기 2 : 라운드가 진행되면 반복 횟수가 줄어듬 (어짜피 정렬이 끝나면 비교할 필요 X)
        // 2. Hard Coding - 특징 찾기 3 : 최대 반복 횟수 : n(n-1) / 2


        // 3. Moduling
        // int i = arr.length -1 (인덱스 넘버는 배열의 총 길이 -1)
        for (int i = arr.length - 1; i > 0; i--) {
            tmp_count = count;
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    count++;
                }
            }
            // 3. Moduling : 반복문 중단을 위한 count 비교 조건문 : 정렬을 진행하였는데 count가 변하지 않음 : 정렬이 완료됨
            if (count == tmp_count) break;
        }

        // 결과 출력
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
        System.out.println("총 정렬 횟수 : " + count);
    }
}

결과

검증

• {7, 5, 3, 1, 2, 4, 6}의 배열을 정렬
1. 7을 정렬하기 위해서는 5, 3, 1, 2, 4, 6과 전부 비교하여 맨 오른쪽으로 정렬해야 함 ( 총 6번 )
2. 5를 정렬하기 위해서는 3, 1, 2, 4와 비교하여 4 오른쪽으로 정렬해야 함 ( 총 4번 )
3. 3을 정렬하기 위해서는 1, 2와 비교하여 2 오른쪽으로 정렬해야 함 ( 총 2번 )
4. 정렬이 완료되었으므로 break. 총 정렬 횟수는 12번으로 동일.