[Algorithm] 버블 정렬 (bubble sort)

Posted: 2022.09.16     Updated: 2022.09.16

버블 정렬(bubble sort)

• 인접한 두 값을 비교해 정렬되어 있지 않다면 값을 교환
• 오름차순으로 정렬할 경우
  • 첫 번째 인덱스와 두 번째 인덱스 비교
    • 첫 번째 인덱스 값이 두 번째 인덱스 값보다 클 경우 값을 교환
    • 두 번째 인덱스 값이 첫 번째 인덱스 값보다 클 경우 교환하지 않음
  • 두 번째 인덱스와 세 번째 인덱스 비교
    • 두 번째 인덱스 값이 세 번째 인덱스 값보다 클 경우 값을 교환
    • 세 번째 인덱스 값이 두 번째 인덱스 값보다 클 경우 교환하지 않음
  • 총 배열의 길이 - 1 번 만큼 반복
  • 마지막 인덱스에 제일 큰 값이 위치하게 됨
  • 마지막 인덱스를 제외하고 나머지 배열 값끼리 위 과정 계속 반복
• 내림차순으로 정렬할 경우
  • 인접한 인덱스를 비교할 때 앞의 값이 뒤의 값보다 작을 경우 교환

예시: {5, 2, 4, 1, 3} 을 오름차순으로 정렬할 경우

• 1회 반복
  • 0번 인덱스 값 5와 1번 인덱스 값 2를 비교, 앞의 값이 크므로 값 교환
  • 배열 상태: {2, 5, 4, 1, 3}
  • 1번 인덱스 값 5와 2번 인덱스 값 4를 비교, 앞의 값이 크므로 값 교환
  • 배열 상태: {2, 4, 5, 1, 3}
  • 2번 인덱스 값 5와 3번 인덱스 값 1을 비교, 앞의 값이 크므로 값 교환
  • 배열 상태: {2, 4, 1, 5, 3}
  • 3번 인덱스 값 5와 4번 인덱스 값 3을 비교, 앞의 값이 크므로 값 교환
  • 배열 상태: {2, 4, 1, 3, 5}
  • 총 4번 비교
  • 배열 내에서 제일 큰 값인 5가 맨 마지막에 위치하게 됨
• 2회 반복
  • 0번 인덱스 값 2와 1번 인덱스 값 4를 비교, 뒤의 값이 크므로 값 교환하지 않음
  • 배열 상태: {2, 4, 1, 3, 5}
  • 1번 인덱스 값 4와 2번 인덱스 값 1을 비교, 앞의 값이 크므로 값 교환
  • 배열 상태: {2, 1, 4, 3, 5}
  • 2번 인덱스 값 4와 3번 인덱스 값 3을 비교, 앞의 값이 크므로 값 교환
  • 배열 상태: {2, 1, 3, 4, 5}
  • 총 3번 비교
  • 정렬 완료된 인덱스를 제외하고 다음으로 큰 값인 4가 정렬됨
• 3회 반복
  • 0번 인덱스 값 2와 1번 인덱스 값 1을 비교, 앞의 값이 크므로 값 교환
  • 배열 상태: {1, 2, 3, 4, 5}
  • 1번 인덱스 값 2와 2번 인덱스 값 3을 비교, 뒤의 값이 크므로 값 교환하지 않음
  • 총 2번 비교
  • 정렬 완료된 인덱스를 제외하고 다음으로 큰 값인 3가 정렬됨
• 4회 반복
  • 0번 인덱스 값 1과 2번 인덱스 값 2를 비교, 뒤의 값이 크므로 값 교환하지 않음
  • 배열 상태: {1, 2, 3, 4, 5}
  • 총 1번 비교
  • 정렬 완료

버블 정렬 자바 코드

public class Sort {

    public void bubbleSort(int[] arr, int size) {
        // 배열 크기 - 1 만큼 반복 실행
        for (int i = 0; i < size - 1; i++) {
            // 전체 한 반복 당 전체 배열 크기-1 에 i를 뺀 만큼 반복하며 비교
            for (int j = 0; j < size - i - 1; j++) {
                // j 번째 값이 다음 값보다 클 경우 값 교환
                if (arr[j] > arr[j+1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
                System.out.println((i+1)+"회 반복 중 "+ (j+1) + "번째 비교: " + Arrays.toString(arr));
            }
        }
    }

}

public class Main {
    public static void main(String[] args) {
        Sort sort = new Sort();
        int size = 5;
        int[] arr = {5, 2, 4, 1, 3};

        sort.bubbleSort(arr, size);

        System.out.println("정렬된 배열: "+ Arrays.toString(arr));
    }
}

출력

1회 반복 중 1번째 비교: [2, 5, 4, 1, 3]
1회 반복 중 2번째 비교: [2, 4, 5, 1, 3]
1회 반복 중 3번째 비교: [2, 4, 1, 5, 3]
1회 반복 중 4번째 비교: [2, 4, 1, 3, 5]
2회 반복 중 1번째 비교: [2, 4, 1, 3, 5]
2회 반복 중 2번째 비교: [2, 1, 4, 3, 5]
2회 반복 중 3번째 비교: [2, 1, 3, 4, 5]
3회 반복 중 1번째 비교: [1, 2, 3, 4, 5]
3회 반복 중 2번째 비교: [1, 2, 3, 4, 5]
4회 반복 중 1번째 비교: [1, 2, 3, 4, 5]
정렬된 배열: [1, 2, 3, 4, 5]

버블 정렬 시간 복잡도

외부 for문 n-1 번, 내부 for문 n-1-j 번 반복하므로 O(n²)