[알고리즘] 버블 정렬(Bubble sort)

 

 

📍버블 정렬이란?

버블 소트는 원소의 이동이 거품이 수면으로 올라오는 듯한 모습이어서 지어진 이름이다. 

 

시간 복잡도가 O(n^2)으로 상당히 느린 정렬 방식이지만,

코드가 단순해서 자주 사용되는 정렬 알고리즘이다.

 

시간 복잡도	비교	교환
최악의 경우	O(n^2)	O(n^2)
최선의 경우	O(n)	O(1)
평균	O(n^2)	O(n^2)

 

배열의 인접한 두 수를 각각 꺼내와 처음부터 비교를 하고, 왼쪽 원소가 오른쪽 원소보다 크다면 두 수를 바꿔주는 작업을 전체 배열에 대해 수행한다. 

그렇게 전체 배열을 다 탐색하게 되면, 가장 큰 원소가 가장 오른쪽에 위치하게 된다.따라서 가장 오른쪽 원소를 제외하고 나머지 원소들에 대해 또 같은 작업을 시행한다. 

작업 단위를 회차라고 했을 때, 배열의 크기가 n인 경우 n-1회차를 진행이 완료되면 전체 배열이 오름차순으로 정렬된다.

---

📍JAVA | 버블 정렬 구현 코드

import java.util.Arrays;

public class bubbleSort {
    static void bubbleSort(int[] arr) {
        for(int i = 0; i < arr.length - 1; i++) {
        //i를 빼줌으로써 탐색 범위를 줄임! (마지막 원소들 잠금 걸어줌)
            for(int j= 1 ; j < arr.length-i; j++) {
                if(arr[j]<arr[j-1]) {
                //바꿔치기
                    int temp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                }
            }
            //각 회전마다 전체 배열 출력
            System.out.println( i+1 +"회전: "+Arrays.toString(arr));

        }
        //전체 배열 출력
        System.out.println("\n정렬된 최종 배열: "+Arrays.toString(arr));

    }

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

 

 

📍실행 결과