BubbleSort(버블정렬) - JAVA

BubblSort의 개념을 간단하게 알아보고, java로 구현해보자.

거품 정렬이란?

• 두 인접한 원소를 검사하며 정렬하는 알고리즘

• 가장 단순한 정렬 알고리즘이지만, 시간복잡도가 O(N^2)으로 상당히느리다.

거품 정렬 과정

인접한 두 원소를 비교하면서 큰 값이 작은값보다 뒤에 위치하도록 정렬한다.

시뮬레이션

[3,4,1,6,7,5] 리스트를 BubbleSort로 정렬해보자.

• 뒤에서부터 정렬을 완성시킨다.

• 매번 첫원소부터 비교하면서, 인접한 원소보다 크다면 뒤에 위치하도록 SWAP해준다.

• 3<4 이므로 건너뛴다.

• 4>1 이므로 SWAP한다.

• 4>6 이므로 건너뛴다.

• 6>7이므로 건너뛴다.

• 5<7이므로 SWAP한다.

이제, 한 STEP이 끝났다. 위의 과정을 list의 길이만큼 반복하면 오름차순 정렬이 완료된다.

• 이어서 정렬 해보자.
• 1>3이므로 SWAP해준다.

• 3<4 이므로 건너뛴다.

• 4<6 이므로 건너뛴다.

• 6>5이므로 SWAP 한다.

• 정렬이 완료되었다.

시간복잡도(Time Complexity)

• O(N^2)

구현

public class bubbleSort {

    static void bubbleSort(int[] list){
        for(int i=0;i<list.length-1;i++){
            for(int j=1;j<list.length-i;j++){
                if(list[j]<list[j-1]){
                    int tmp=list[j];
                    list[j]=list[j-1];
                    list[j-1]=tmp;
                }
            }
        }
    }

    public static void main(String[] args){
        int[] list={3,4,1,6,7,5};
        bubbleSort(list);
    }
}

Reference

• 거품정렬 - 위키백과