[JAVA] 버블정렬(Bubble Sort) 개념과 코드 구현

버블정렬(Bubble Sort)이란 이웃한 두 요소의 대소관계를 비교해서 교환을 반복하는 정렬 알고리즘이다.

시간 복잡도가 느리지만 코드가 단순하다.

구분	최악 시간복잡도	최선 시간복잡도	평균 시간복잡도	공간복잡도(메모리)	안정성
버블정렬	O(n^2)	O(n^2)	O(n^2)	O(1)	Y

 

알고리즘

1. 배열의 첫번째 원소부터 비교를 시작한다.

2. 현재 원소와 다음 요소의 크기를 비교한다.

3. 현재 요소가 다음 원소보다 크다면 두 원소를 교환한다.

4. 이 과정을 배열의 끝까지 반복한다.

5. 배열의 첫번째 자리에서 부터 [마지막 원소 - (반복횟수)] 자리까지 반복한다.

6. 정렬하는 과정을 배열의 길이 -1 번 반복하면 모든 원소가 정렬된다.

 

소스코드(Ver 1)

public static int[] bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

 

소스코드(Ver 2)

만약 배열을 순회하는 과정에서 중간에 이미 정렬이 완료되었을 경우 정렬을 종료하는 코드이다.

public static int[] bubbleSort(int[] arr) {
    int arrLength = arr.length;

    for(int i = 0; i < arrLength; i++) {
        // swap 횟수를 기록한다.
        // 어떤 요소도 swap되지 않은 경우, 배열은 정렬된 상태이다.
        int swaps = 0;

        for(int j = 0; j < arrLength - 1; j++) {
            if(arr[j] > arr[j+1]) {
                swaps++;
                arr = swap(j, j+1, arr);
            }
        }
        // swap된 횟수가 없으면 정렬이 모두 완료된 상태이므로 반복문을 종료한다.
        if(swaps == 0) {
            break;
        }
    }
    return arr;
}

// 배열에서 두 요소의 위치를 교환하는 메서드
public static int[] swap(int idx1, int idx2, int[] arr) {
    //두 변수를 바꾸는 방법
    int temp = arr[idx1];
    arr[idx1] = arr[idx2];
    arr[idx2] = temp;

    return arr;
}