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

# 요약

• 서로 인접한 두원소를 검사하여 정렬하는 알고리즘
  • 인접한 2개의 데이터를 비교하여 크기가 순서대로 되어있지 않으면 SWAP한다.
• 선택 정렬과 기본 개념이 유사

 

# 구체적 설명

• 버블 정렬은 1번째 데이터와 2번째 데이터, 2번째 데이터와 3번째 데이터, 3번째 데이터와 4번째 데이터를 비교한다.
  즉,  n과 n+1을 비교하며 조건에따라 SWAP을 진행한다..
• 1회전을 수행하고 나면 오름차순, 내림차순에 따라 자료가 정렬이 진행된다.

 

# 알고리즘

https://medium.com/karuna-sehgal/an-introduction-to-bubble-sort-d85273acfcd8

# 코드 작성 -  JAVA

import java.util.Arrays;

public class sort_bubble {
    static int[] arr = new int[]{7, 1, 3, 2, 4, 5, 6}; //정렬 대상

    public static void main(String[] args) {
        sortBubble(arr); //버블 정렬
        System.out.println(Arrays.toString(arr));
    }

    private static void sortBubble(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            System.out.printf("%d 라운드 ", i); //해당라운드 수
            System.out.println();
            for (int j = 0; j < arr.length - 1; j++) {
                System.out.printf("%d 비교 횟수", arr.length - i); //비교횟수
                System.out.println();
                if (arr[i] < arr[j]) {
                    swap(i, j); //swap
                }
            }
        }
    }

    private static void swap(int i, int j) { //swap함수
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

 

# 결과

1 라운드 6 비교 횟수
2 라운드 5 비교 횟수
3 라운드 4 비교 횟수
4 라운드 3 비교 횟수
5 라운드 2 비교 횟수
6 라운드 1 비교 횟수
[1, 2, 3, 4, 5, 6, 7]

 

 

#시간복잡도

최선	O(n^2)
평균	O(n^2)
최악	O(n^2)

 

 

#장단점

장점	단점
구현이 매우 간단하고, 소스코드가 직관적 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요X => 제자리 정렬(in-place sorting) 안정 정렬(Stable Sort)	시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로 굉장히 비효율 정렬 돼있지 않은 원소가 정렬 됐을때의 자리로 가기 위해서, 교환 연산(swap)이 많이 발생

---