버블 정렬 (Bubble Sort)
- ETC
- 2018. 12. 6.
버블 정렬 (Bubble Sort)
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 |
▪︎ 첫 번째 탐색 (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장. 정렬문제> - 강영경 교수
✔︎ 오타, 틀린 개념이 있을 경우 댓글 달아주세요~!
(확인 후 수정하도록 하겠습니다~^^)
✔︎ 추가할 개념이 있다면 댓글 부탁드립니다~!
(지식을 공유해주세요~^^)