알고리즘 공부

[정렬] Bubble Sort (버블정렬) - Java

Developer KTU 2024. 9. 5. 16:27
반응형

1. 버블정렬이란?

인접한 두 요소를 비교하여 정렬하는 간단한 알고리즘이다. 왜 버블정렬일까? 가장 큰 요소가 배열의 마지막 위치로 버블처럼 떠오른다고 하여 '버블정렬' 이라는 이름으로 유래됨.

 

2. 시간복잡도

각 정렬 과정마다 다시 한번 배열을 순회하여 인접한 두 요소를 비교해야 하므로 O(N^2) 의 시간복잡도를 가진다.

 

3. 핵심이론

1) 배열 사이즈가 N이라고 가정한다.

2) 버블 정렬은 총 (N - 1)번의 과정을 거친다.

3) 각 정렬 과정마다 맨 끝 요소는 정렬이 된 상태이므로 (N - i - 1)번 순회한다.

4) 이전 요소가 다음 요소보다 크면 swap 진행

5) 위 과정 반복

 

4. 예시

아래 N이라는 배열이 있다고 가정하자.

5 4 3 2 1

1) 첫번째 순회

4 5 3 2 1
4 3 5 2 1
4 3 2 5 1
4 3 2 1 5
(가장 큰 요소가 배열의 끝에 옴)

첫번째 순회는 총 4번 (N - 0 - 1) 번 진행한다.

 

2) 두번째 순회

3 4 2 1 5
3 2 4 1 5
3 2 1 4
(그 다음 큰 요소가 배열의 끝에 옴)
5
(이미 정렬 완료)

두번째 순회는 총 3번 (N - 1 - 1)번 순회한다.

 

3) 세번째 순회

2 3 1 4 5
2 1 3
(그 다음 큰 요소가 배열의 끝에 옴)
4
(이미 정렬 완료)
5
(이미 정렬 완료)

세번째 순회는 총 2번 (N - 2 - 1)번 순회한다.

 

4) 네번째 순회

1 2
(그 다음 큰 요소가 배열의 끝에 옴)
3
(이미 정렬 완료)
4
(이미 정렬 완료)
5
(이미 정렬 완료)

총 네 번 (N - 1번)의 정렬 과정의 (N - i - 1)번의 비교 과정으로 버블정렬은 종료된다.

 

예시 코드

public class Main {
    public static void bubbleSort(int[] arr){
        // 버블정렬 수행
        for(int i = 0; i < arr.length - 1; i++){
            for(int j = 0; j < arr.length - i - 1; j++){
                if(arr[j + 1] < arr[j]){
                    swap(arr, j + 1, j);
                }
            }
        }
    }
	
    // swap 함수
    public static void swap(int[] arr, int t1, int t2){
        int temp = arr[t1];
        arr[t1] = arr[t2];
        arr[t2] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {5, 4, 3, 2, 1};

        bubbleSort(arr);

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}
출력 결과 : 1 2 3 4 5

 

반응형