[Algorithm] Bubble Sort

Stable Sort

---

정렬 방식

상당히 간단한 정렬 알고리즘이다. 그냥 인접한 두 수끼리 크기를 비교해서 왼쪽값이 오른쪽값보다 크면 서로 exchange해주면 된다

이렇게 정렬하면 매번 정렬할 때마다 최댓값은 알아서 오른쪽에 순차적으로 정렬된다

 

43

1

25

9

16

 

▶ Round 1

43

1

25

9

16

---

1

43

25

9

16

---

1

25

43

9

16

---

1

25

9

43

16

---

1

25

9

16

43

 

▶ Round 2

1

25

9

16

43

 

1

25

9

16

43

 

1

9

25

16

43

 

1

9

16

25

43

---

Java Code

static void bubble_sort(int [] list, int n){
    for(int i = n - 1; i >= 0; i--){
        for(int j = 0; j < i; j++){
            if(list[j] > list[j + 1]){
                int tmp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = tmp;
            }
        }
    }
}

 

시간복잡도 분석 (상수는 C로 간주 & Worst Case 기준)

1) 가장 안쪽 for문부터 분석

for(int j = 0; j < i; j++){
    if(list[j] > list[j + 1]){
        int tmp = list[j];
        list[j] = list[j + 1];
        list[j + 1] = tmp;
    }
}

- for문 내에 연산 개수 : C개 (상수)

- for문 루프 횟수 : (i-1) + 1 = i번

>> C₁i

 

2) 바깥쪽 for문 분석

for(int i = n - 1; i >= 0; i--){
    for(int j = 0; j < i; j++){
        if(list[j] > list[j + 1]){
            int tmp = list[j];
            list[j] = list[j + 1];
            list[j + 1] = tmp;
        }
    }
}

- for문 내 연산 개수 : C₁i번

- for문 루프 : 0 ~ n-1

 

3) 최종 시간복잡도

---

Example Code

package Sort;

/*
인접한 두 수끼리 계속 비교해서 최종적으로 정렬
 */

public class Bubble_Sort_10 {
    public static void main(String[] args) {
        int [] list = new int[30]; // 정렬할 배열 list

        for(int i=0; i<list.length; i++)
            list[i] = (int)(Math.random()*201); // 0~200

        // 정렬 전 list 출력
        System.out.print("정렬 전 list []");
        for(int i=0; i<list.length; i++){
            if(i%10==0) System.out.println();
            System.out.print(list[i] + "\t");
        }
        System.out.println("\n");

        bubble_sort(list, list.length);

        // 정렬 후 list 출력
        System.out.print("정렬 후 list []");
        for(int i=0; i<list.length; i++){
            if(i%10==0) System.out.println();
            System.out.print(list[i] + "\t");
        }
        System.out.println("\n");
    }

    static void bubble_sort(int [] list, int n){
        for(int i = n - 1; i >= 0; i--){
            for(int j = 0; j < i; j++){
                if(list[j] > list[j + 1]){
                    int tmp = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = tmp;
                }
            }
        }
    }
}