[Sort] 거품 정렬 (Bubble Sort | Java)

Bubble Sort

N개의 원소를 가진 배열을 정리할 때, 서로 인접한 두 개의 데이터를 비교하고, 조건에 맞춰 자리를 교환하며 정리하는 알고리즘입니다. 시간 복잡도가 O(n^{2})로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용되며. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름입니다.

예시 1

void bubbleSort(int[] arr) {
    int temp = 0;
    for(int i = 0; i < arr.length; i++) {       // 1.
        for(int j= 1 ; j < arr.length-i; j++) { // 2.
            if(arr[j-1] > arr[j]) {             // 3.
                // swap(arr[j-1], arr[j])
                temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

예시 2

public int[] sort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
                Utils.swapValue(arr, i, j);
            }
        }
    }
    return arr;
}

시간 복잡도

Space Complexity	Time Complexity
O(1)	O(n^2)

장점

• 구현이 간단하고, 코드가 직관적
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않다. => 제자리 정렬(in-place sorting)
• 안정 정렬(Stable Sort)이다.

단점

• 시간 복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적
• 정렬돼있지 않은 원소가 정렬됐을 때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어남

참고자료

거품 정렬 - 위키백과, 우리 모두의 백과사전

 

거품 정렬(Bubble Sort) | 👨🏻‍💻 Tech Interview

 

GitHub - JaeYeopHan/Interview_Question_for_Beginner: Technical-Interview guidelines written for those who started studying progr