기본 정렬 알고리즘 구현: 버블 정렬 (Java)

버블 정렬

 

버블 정렬

- 버블정렬 또는 거품 정렬(bubble sort, sinking sort)

원소 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름

 

시간 복잡도

최선: O(n^2)

최악: O(n)

 

시간 복잡도

 

특징

코드 단순

 

기본 과정

1. 비교와 교환

• 배열에서 인접한 두 수(a, b)를 선택
• 오름차순 정렬: a > b라면 두 수를 교환, 그렇지 않으면 그대로 둠.
• 내림차순 정렬: a < b라면 교환, 그렇지 않으면 그대로 둠

2. 한 바퀴 반복

• 배열의 처음부터 끝까지 이 과정을 진행하면, 가장 큰 값(오름차순) 또는 가장 작은 값(내림차순)이 배열의 끝으로 이동

3. 전체 반복

• 이 과정을 배열에 더 이상 교환이 필요 없을 때 까지(즉, 배열이 완전히 정렬될 때까지) 반복
  • 한 바퀴를 돌았을 때 단 한번도 교환이 일어나지 않았다면, 배열이 이미 정렬된 상태라는 뜻
  • 이를 최적화라고 하며, 불필요한 반복을 줄이기 위해 플래그 변수를 사용

 

코드(오름차순)

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped; // 교환 여부를 체크하는 플래그

        for(int i = 0; i < n - 1; i++) { // 외부 반복문
            swapped = false;
            for(int j = 0; j < n -1 - i; j++) { // 내부 반복문
                if(arr[j] > arr[j+1]) { // 오름차순: a > b면 교환
                    // 교환
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    swapped = true;
                }
            }
            // 교환이 없으면 정렬 완료
            if(!swapped) break;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 1, 2};
        bubbleSort(arr);
        for(int  num : arr) {
            System.out.println(num+   " ");;
        }
    }
}