버블 정렬 (Bubble Sort)

버블 정렬 (Bubble Sort)

✐ 개념

인접한 2개의 레코드를 비교하여 순서가 맞지 않으면 서로 교환하는 비교-교환 과정을

리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행하는 방식으로 정렬하는 방법 (제자리 정렬, 안정적 정렬)

<단순하지만 비효율적인 방법>

✐ 시간 복잡도 : T(n) = (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n^2)

✐ Java 코드

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

✐ 코드 해석

✓ data = { 2, 9, 5, 4, 8, 1 }

    위와 같이 크기가 6인 배열의 예시가 있다.

▪︎ 첫 번째 탐색 (1st pass)

▫︎ (4번 라인) i = 5

▫︎ (5번 라인) j = 0

▫︎ (6번 라인) if(data[0] > data[1]) 결과 값이 (2 < 9)이므로 조건 불일치

▫︎ (4번 라인) i = 5

▫︎ (5번 라인) j = 1

▫︎ (6번 라인) if(data[1] > data[2]) 결과 값이 (9 > 5)이므로 조건 일치

▫︎ (7번 ~ 9번 라인) { 2, 9, 5, 4, 8, 1 } ☛ swap ☛ { 2, 5, 9, 4, 8, 1 }

▫︎ (4번 라인) i = 5

▫︎ (5번 라인) j = 2

▫︎ (6번 라인) if(data[2] > data[3]) 결과 값이 (9 > 4)이므로 조건 일치

▫︎ (7번 ~ 9번 라인) { 2, 5, 9, 4, 8, 1} ☛ swap ☛ {2, 5, 4, 9, 8, 1}

▫︎ (4번 라인) i = 5

▫︎ (5번 라인) j = 3

▫︎ (6번 라인) if(data[3] > data[4]) 결과 값이 (9 > 8)이므로 조건 일치

▫︎ (7번 ~ 9번 라인) { 2, 5, 4, 9, 8, 1 } ☛ swap ☛ { 2, 5, 4, 8, 9, 1 }

▫︎ (4번 라인) i = 5

▫︎ (5번 라인) j = 4

▫︎ (6번 라인) if(data[4] > data[5]) 결과 값이 (9 > 1)이므로 조건 일치

▫︎ (7번 ~ 9번 라인) { 2, 5, 4, 8, 9, 1 } ☛ swap ☛ { 2, 5, 4, 8, 1, 9 }

▪︎ 두 번째 탐색 (2nd pass)

▫︎ (4번 라인) i = 4

▫︎ (5번 라인) j = 0

▫︎ (6번 라인) if(data[0] > data[1]) 결과 값이 (2 < 5)이므로 조건 불일치

▫︎ (4번 라인) i = 4

▫︎ (5번 라인) j = 1

▫︎ (6번 라인) if(data[1] > data[2]) 결과 값이 (5 > 4)이므로 조건 일치

▫︎ (7번 ~ 9번 라인) { 2, 5, 4, 8, 1, 9 } ☛ swap ☛ { 2, 4, 5, 8, 1, 9 }

▫︎ (4번 라인) i = 4

▫︎ (5번 라인) j = 2

▫︎ (6번 라인) if(data[2] > data[3]) 결과 값이 (5 < 8)이므로 조건 불일치

▫︎ (4번 라인) i = 4

▫︎ (5번 라인) j = 3

▫︎ (6번 라인) if(data[3] > data[4]) 결과 값이 (8 > 1)이므로 조건 일치

▫︎ (7번 ~ 9번 라인) { 2, 4, 5, 8, 1, 9 } ☛ swap ☛ { 2, 4, 5, 1, 8, 9 }

▪︎ 세 번째 탐색 (3rd pass)

▫︎ (4번 라인) i = 3

▫︎ (5번 라인) j = 0

▫︎ (6번 라인) if(data[0] > data[1]) 결과 값이 (2 < 4)이므로 조건 불일치

▫︎ (4번 라인) i = 3

▫︎ (5번 라인) j = 1

▫︎ (6번 라인) if(data[1] > data[2]) 결과 값이 (4 < 5)이므로 조건 불일치

▫︎ (4번 라인) i = 3

▫︎ (5번 라인) j = 2

▫︎ (6번 라인) if(data[2] > data[3]) 결과 값이 (5 > 1)이므로 조건 일치

▫︎ (7번 ~ 9번 라인 ) { 2, 4, 5, 1, 8, 9 } ☛ swap ☛ { 2, 4, 1, 5, 8, 9 }

▪︎ 네 번째 탐색 (4th pass)

▫︎ (4번 라인) i = 2

▫︎ (5번 라인) j = 0

▫︎ (6번 라인) if(data[0] > data[1]) 결과 값이 (2 < 4)이므로 조건 불일치

▫︎ (4번 라인) i = 2

▫︎ (5번 라인) j = 1

▫︎ (6번 라인) if(data[1] > data[2]) 결과 값이 (4 > 1)이므로 조건 일치

▫︎ (7번 ~ 9번 라인) { 2, 4, 1, 5, 8, 9 } ☛ swap ☛ { 2, 1, 4, 5, 8, 9 }

▪︎ 다섯 번째 탐색 (5th pass)

▫︎ (4번 라인) i = 1

▫︎ (5번 라인) j = 0

▫︎ (6번 라인) if(data[0] > data[1]) 결과 값이 (2 > 1)이므로 조건 일치

▫︎ (7번 ~ 9번 라인) { 2, 1, 4, 5, 8, 9 } ☛ swap ☛ { 1, 2, 4, 5, 8, 9 }

✓ 한 눈에 보기

✐ 코드 결과

숫자를 오름차순으로 정렬하는 버블 정렬이다.

최종적으로 출력되는 결과 값은 { 1, 2, 4, 5, 8, 9 }이다.

References. 2017 알고리즘 강의 <1장. 정렬문제> - 강영경 교수

✔︎ 오타, 틀린 개념이 있을 경우 댓글 달아주세요~!

(확인 후 수정하도록 하겠습니다~^^)

✔︎ 추가할 개념이 있다면 댓글 부탁드립니다~!

(지식을 공유해주세요~^^)