버블 정렬(Bubble Sort)

Algorithmday_4 정리 (2021.12.01 수요일)

버블 정렬(Bubble Sort)

• 인접한 항목이 순서대로 되어 있지 않으면 서로 교환한다.
  • a = [7,6,5,2,1,4,8,9,3] 원본
  • a = [6,7,5,2,1,4,8,9,3] 7, 6 교환
  • a = [6,5,7,2,1,4,8,9,3] 7, 5 교환
  • a = [6,5,2,7,1,4,8,9,3] 7, 2 교환
  • a = [6,5,2,1,7,4,8,9,3] 7, 1 교환
  • a = [6,5,2,1,4,7,8,9,3] 7, 4 교환
  • a = [6,5,2,1,4,7,8,3,9] 7, 8 / 7, 9는 맞기 때문에 건너 뛰고(하지만 비교는 하기 때문에 성능에 영향을 끼친다.) 9, 3 교환
  • 까지 1라운드 종료 -> 다시 a[0], a[1]비교부터 시작
  • a = [5,6,2,1,4,7,8,3,9] 6, 5 교환
  • .....
  • a = [1,2,3,4,5,6,7,8,9] 가 될 때 까지 반복 위와 같은 과정 반복
  • 항목이 n개인 배열에 정렬을 하면 비교 횟수는 n(n-1)/2번의 비교를 한다.

 

 

버블 정렬 예제 코드

• BubbleSort.java

public class BubbleSort {
    public static void main(String[] args) {
        int [] arr = {5,2,8,3,1};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    static void bubbleSort(int[] arr) {
        // 이전 값을 뒤에 넣기 위해 임시 저장소 필요
        int temp = 0;
        // 총 라운드 : 배열 크기 - 1번
        for(int i = 0; i < arr.length; i++) {
            // 각 라운드별 비교 횟수 : 배열크기 - 라운드 횟수
            for(int j = 0; j < arr.length-1-i; j++) {
                if(arr[j] > arr[j+1]) {
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
}