티스토리 뷰

Algorithm

버블 정렬 (Bubble Sort)

WHITEPAEK 2018.12.06 00:26

버블 정렬 (Bubble Sort)

 개념
인접한 2개의 레코드를 비교하여 순서가 맞지 않으면 서로 교환하는 비교-교환 과정을
리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행하는 방식으로 정렬하는 방법 (제자리 정렬, 안정적 정렬)
<단순하지만 비효율적인 방법>

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

 Java 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
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;
            }
        }
    }
}
cs

 코드 해석
✓ 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]) 결과 값이 (> 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, 14, 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장. 정렬문제> - 강영경 교수




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

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


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

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

'Algorithm' 카테고리의 다른 글

버블 정렬 (Bubble Sort)  (0) 2018.12.06
선택 정렬 (Selection Sort)  (0) 2018.12.04
이진 탐색 (Binary Search)  (0) 2018.12.01
순차 탐색 (Liner Search)  (0) 2018.11.29
재귀 함수 (Recursion Function)  (0) 2018.11.29
알고리즘 분석 (Algorithm analysis)  (0) 2018.11.29
댓글
댓글쓰기 폼
«   2019/07   »
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      
Total
161,450
Today
15
Yesterday
473