버블 정렬(Bubble Sort)

개념

서로 인접해 있는 요소 간 대소 비교를 통해 정렬하는 알고리즘입니다. 

추가적인 메모리 공간이 필요하지 않다는 특징이 있으며 

쉽게 구현할 수 있지만 비효율적인 알고리즘입니다. 

 

인접한 원소를 교환하는 모습이 마치 물 속의 거품과 비슷하다고하여 버블 정렬이라고 부른다고 합니다.

 

로직

예시로 오름차순 정렬을 만든다면

arr = [1, 7, 2, 4, 5, 6]

 

N-1개의 요소를 순회하며(0 ~ N-2 인덱스)

현재 인덱스에 위치한 값이(a) 다음 인덱스에 위치한 값(b) 보다 클 경우 교환해줍니다.

이렇게 첫번째 순회를 마치게 되면 결과는

다음과 같이 수열 중 가장 큰 수인 7이 맨 오른쪽으로 정렬된 것을 볼 수 있습니다.

arr = [1, 2, 4, 5, 6, 7]

 

해당 예시는 한 번의 정렬만으로 오름차순 정렬이 완료된 운이 좋은 케이스이지만

버블 정렬 특성상 도중에 정렬이 완료되어도 멈추는 로직이 없기 때문에 N번 순회가 이루어집니다.

(도중에 정렬이 완성되어 멈추는 로직을 작성해 놓는다면 빨라질 수도 있지만, 최악의 케이스에서는 모든 과정을 체크해야 하므로 오히려 비효율적일 것입니다.)

 

코드

자바로 작성한 버블정렬 코드는 다음과 같습니다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        int[] arr = {5, 4, 2, 1, 3, 6};
        int N = arr.length;
        int cnt = 0;
        
        // 일반적인 버블 소트: (N-1)^2 순회
        for(int i = 0 ; i < N-1 ; i ++){
            for(int j = 0 ; j < N-1 ; j ++){
                cnt ++;
                if(arr[j] > arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }

        // 한번 순회를 마치면 최소 한자리 수는 정렬되므로
        // 그 다음 순회에서는 정렬된 한 칸을 제외한 순회를 진행한다.
        // (N-1)! 순회
        for(int i = 0 ; i < N-1 ; i ++){
            for(int j = 0 ; j < N-1-i ; j ++){
                cnt ++;
                if(arr[j] > arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
        
        System.out.println(cnt);
        System.out.println(Arrays.toString(arr));
    }
}

 

따라서 시간 복잡도는

O(N^2) 입니다.