알고리즘 - 버블 정렬 (Bubble Sort)

안녕하세요, 알고리즘을 정리하는 포스팅입니다. 다른 알고리즘을 참고하시려면 해당 카테고리를 이용해주세요. 😊

'🌻 JAVA/알고리즘, 자료구조' 카테고리의 글 목록

 

 

버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 원소를 비교해 자리를 바꿔나가면서 정렬하는 알고리즘입니다.

 

시간 복잡도 : O(N^2)
공간 복잡도 : O(N)
안정 정렬

 

과정

1. 첫 번째 원소부터 마지막 원소까지 차례대로 인접한 원소를 비교합니다.
2. 서로 비교하여 앞 원소가 더 크다면 서로 위치를 교환해줍니다.
3. 이렇게 한 사이클이 완료가 되면, 해당 사이클에 마지막에 위치시킨 원소는 정렬이 완료된 것을 알 수 있습니다. (중요 : 아래에서 설명)

 

Code

위에서 설명한 과정을 순서대로 코드로 표현해보겠습니다.

 

1. 먼저 첫 번째 원소부터 마지막 원소까지 차례대로 인접한 원소를 비교합니다.

1번 과정을 코드로 옮기기 전에 해당 사이클은 총 몇 번이 반복되어야 할까요? 바로 N-1번입니다. 마지막 원소는 비교할 대상이 없기 때문에 -1을 해준 것입니다.

3번 과정을 보면 한 사이클이 끝나면 마지막 원소는 이미 정렬이 완료된 상태이기 때문에 굳이 정렬이 완료된 원소를 탐색할 필요가 없습니다.

그렇기 때문에 범위는 아래와 같이 됩니다.

for(int i=1; i < N; i++) {
    for(int j=0; j<N-i; j++) {
    // 첫 번째 원소부터 마지막-i 원소까지 비교!
    }
}

전체적으로 사이클은 N-1번 반복되고, 내부의 for문은 첫 번째 원소부터 N-i 번째 원소까지 비교를 해나가면 되겠습니다.

 

2. 서로 비교하여 앞 원소가 더 크다면 위치를 교환해줍니다.

if( arr[j] > arr[j+1] ) {
    temp = arr[j];
    arr[j] = arr[j+1];
    arr[j+1] = temp;
}

 

 

전체 코드

public void bubble_Sort(int[] arr) {
    int temp = 0;
    int N = arr.length;
    
    for(int i=1; i<N; i++) {
    	for(int j=0; j<N-i; j++) {
            if(arr[j] > arr[j+1]) {
            	temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}