[Data Structure] 버블 정렬 - Bubble Sort

버블 정렬 (Bubble Sort)

Stable Sort

• 인접한 두 정수를 비교해서 정렬

 

시간복잡도

- O(n²)

 

장점

- 구현이 매우 간단하다

- 추가 메모리가 필요없다

 

단점

- 시간복잡도가 최선/평균/최악 전부 O(n²)으로, 굉장히 비효율적이다

 

 

▶ Bubble Sort Code

static void bubble_sort(int [] A){
        Calendar before = Calendar.getInstance();
        for(int i=0; i<A.length; i++){
            for(int j=0; j<A.length-1; j++){
                if(A[j] > A[j+1]){
                    int tmp = A[j];
                    A[j] = A[j+1];
                    A[j+1] = tmp;
                }
            }
        }
    }

 

 

▶ Full Code

package Sort;

import java.util.Calendar;

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

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

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

        bubble_sort(A);

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

    static void bubble_sort(int [] A){
        Calendar before = Calendar.getInstance();
        for(int i=0; i<A.length; i++){
            for(int j=0; j<A.length-1; j++){
                if(A[j] > A[j+1]){
                    int tmp = A[j];
                    A[j] = A[j+1];
                    A[j+1] = tmp;
                }
            }
        }
    }
}