버블 정렬
코드 설계
- 배열의 왼쪽에서 오른쪽으로 여러번 스캔
- 스캔 시 인접한 배열의 값과 비교하여 인덱스가 큰 배열의 요소 값보다 인덱스 값이 작은 배열의 요소의 값이 클 경우 위치를 바꾼다.
* 2, 7, 4, 1, 5, 3
1차 -> 2, 4, 1, 5, 3, 7
2차 -> 2, 1, 4, 3, 5, 7
3차 -> 1, 2, 3, 4, 5, 7
// pseudo-code
BubbleSort(A, n) {
for k <- 1 to n-1 {
for i <- 0 to n-2 {
if( A[i] > A[i+1]) {
swap(A[i], A[i+1])
}
}
}
}
// pseudo-code
BubbleSort(A, n) {
for k <- 1 to n-1 {
flag <- 0
for i <- 0 to n-k {
if( A[i] > A[i+1]) {
swap(A[i], A[i+1])
flag <- 1
}
}
if (flag == 0) break
}
}
코드 구현
public int[] bubbleSort(int[] A, int n) {
int[] ret;
for(int k = 1 ; k < n ; k++) { // 1 ~ n - 1 까지
for(int i = 0 ; i < n - 1 ; i++) { // 0부터 n - 2 까지
if(A[i] > A[i+1]) {
int tmp = A[i];
A[i] = A[i+1];
A[i+1] = tmp;
// 과정 출력
}
}
}
ret = A;
return ret;
}
0: 2 7 4 1 5 3
1: 2 4 7 1 5 3
2: 2 4 1 7 5 3
3: 2 4 1 5 7 3
4: 2 4 1 5 3 7
0: 2 4 1 5 3 7
1: 2 1 4 5 3 7
2: 2 1 4 5 3 7
3: 2 1 4 3 5 7
4: 2 1 4 3 5 7
0: 1 2 4 3 5 7
1: 1 2 4 3 5 7
2: 1 2 3 4 5 7
3: 1 2 3 4 5 7
4: 1 2 3 4 5 7
0: 1 2 3 4 5 7
1: 1 2 3 4 5 7
2: 1 2 3 4 5 7
3: 1 2 3 4 5 7
4: 1 2 3 4 5 7
0: 1 2 3 4 5 7
1: 1 2 3 4 5 7
2: 1 2 3 4 5 7
3: 1 2 3 4 5 7
4: 1 2 3 4 5 7
- swap이 없는 경우 loop에서 벗어나는 flag 설정
public int[] bubbleSort1(int[] A, int n) {
int[] ret;
boolean flag = false;
for(int k = 1 ; k < n ; k++) { // 1 ~ n - 1 까지
flag = false;
for(int i = 0 ; i < n - k ; i++) { // 0부터 n - k 까지
if(A[i] > A[i+1]) {
int tmp = A[i];
A[i] = A[i+1];
A[i+1] = tmp;
flag = true;
// 과정 출력
}
}
if(!flag) break;
}
ret = A;
return ret;
}
1: 2 4 7 1 5 3
2: 2 4 1 7 5 3
3: 2 4 1 5 7 3
4: 2 4 1 5 3 7
1: 2 1 4 5 3 7
3: 2 1 4 3 5 7
0: 1 2 4 3 5 7
2: 1 2 3 4 5 7
int[] A = {2, 7, 4, 1, 5, 3};
int n = A.length;
@Test
public void testBubble() {
int[] except = {1, 2, 3, 4, 5, 7};
assertThat(bubbleSort(A, n), is(except));
}
@Test
public void testBubble1() {
int[] except = {1, 2, 3, 4, 5, 7};
assertThat(bubbleSort1(A, n), is(except));
}
분석
- 복잡도 분석
- Bast-Case O(n)
- Average-Case O(n^2)
- Worst-Case O(n^2)
- 선택 정렬만큼 우수하지만 마찬가지로 느린 정렬 방식
