[알고리즘] 버블 정렬 BubbleSort

정렬 알고리즘이란?

정렬 알고리즘은 배열의 원소들을 조건에 맞게 순서대로 정렬하는 알고리즘입니다. 원소들이 어떤 순서로 들어오는지에 따라 적절한 정렬 알고리즘을 선택할 수 있습니다.

선택 기준

1. 시간 복잡도: 알고리즘이 실행되는 데 소요되는 시간
2. 공간 복잡도: 알고리즘이 사용하는 메모리의 양
3. 안전성 (Stability): 동일한 값의 원소들의 순서가 유지되는지 여부

정렬 알고리즘 종류와 시간 복잡도

정렬 알고리즘 종류	최선 시간 복잡도	평균 시간 복잡도	최악 시간 복잡도
BubbleSort (버블 정렬)	O(n)	O(n^2)	O(n^2)
SelectionSort (선택 정렬)	O(n^2)	O(n^2)	O(n^2)
InsertionSort (삽입 정렬)	O(n)	O(n^2)	O(n^2)
MergeSort (병합 정렬)	O(n log n)	O(n log n)	O(n log n)
RadixSort (기수 정렬)	O(nk)	O(nk)	O(nk)
QuickSort (퀵 정렬)	O(n log n)	O(n log n)	O(n^2)

 

현재 정렬을 사용할 때는 대부분 퀵 정렬을 사용합니다. 병합 정렬이 최악의 조건에서 더 빠를 것 같다고 생각할 수 있지만, 정렬 알고리즘을 선택할 때는 시간 복잡도뿐만 아니라 공간 복잡도도 고려해야 합니다.

병합 정렬은 메모리를 많이 사용하므로, 여러 가지를 고려하여 정렬 알고리즘을 선택해야 합니다.

 

 

BubbleSort (버블 정렬)이란?

가장 기초적인 정렬 알고리즘으로, 정렬 알고리즘 중에서 구현하기 가장 쉬운 방법입니다.

인접한 두 개의 원소를 비교하여, 조건에 맞게 위치를 교환하며 정렬하는 방식입니다.

원소들이 거품(버블)처럼 배열의 끝으로 이동하는 것처럼 보이기 때문에 버블 정렬이라는 이름이 붙었습니다.

이 알고리즘은 2중 for문을 사용하며, 한 번 배열을 순회할 때마다 큰 수 혹은 작은 수가 배열의 끝으로 이동합니다.

 

오름차순으로 정렬해보기

배열의 0번째 원소부터 시작하여, 인접한 원소들을 비교하고 조건에 맞게 위치를 교환(swap)합니다.

 

예시:

0번째와 1번째 위치 비교 후, 조건에 맞으면 swap

3

1

4

2

1

3

4

2

 

1번째와 2번째 위치 비교 (조건에 맞지 않아 swap하지 않음)

1

3

4

2

 

2번째와 3번째 위치 비교 후, 조건에 맞으면 swap

1

3

2

4

배열의 끝까지 확인한 후, 다시 처음으로 돌아가서 과정을 반복합니다.

1

3

2

4

1

2

3

4

 

 

코드로 작성하기

직접 하시고 싶은 분들이 있을 수 있으니 코드는 숨기겠습니다.

코드를 보고 싶다면 더보기 클릭:

// 두 원소의 위치를 교환하는 메소드
public static void swap(int[] arr, int i, int j) {
    // 임시 변수에 arr[i] 값을 저장합니다.
    int tmp = arr[i];
    // arr[i]에 arr[j] 값을 저장합니다.
    arr[i] = arr[j];
    // arr[j]에 임시 변수에 저장된 값을 저장합니다.
    arr[j] = tmp;
}

import java.util.Arrays;

public class Main {
    
    public static void main(String[] args) {
        // 정렬할 배열을 정의합니다.
        int[] arr = {5, 1, 9, 4, 6, 2, 7, 8, 3, 10};
        
        // 버블 정렬을 호출하여 배열을 정렬합니다.
        bubbleSort(arr);
        
        // 정렬된 배열을 출력합니다.
        System.out.println(Arrays.toString(arr));
    }
    
    // 버블 정렬 알고리즘을 구현한 메소드
    public static void bubbleSort(int[] arr) {
        // 배열의 모든 원소를 확인합니다.
        for (int i = 0; i < arr.length - 1; i++) {
            // 배열의 끝까지 반복하며 인접한 원소를 비교합니다.
            for (int j = 0; j < arr.length - 1; j++) {
                // 인접한 원소가 정렬 순서에 맞지 않으면 교환합니다.
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }
    
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

 

버블정렬 최적화 해보기

1. 불필요한 반복 감소:
   • 기존 버블 정렬은 배열의 모든 원소를 매번 끝까지 반복하여 비교했습니다.
   • 최적화된 코드에서는 이미 정렬된 원소가 배열의 끝에 위치하므로, 반복의 범위를 줄여 arr.length - 1 - i까지 검사합니다.
   • 이렇게 하면 각 반복이 끝날 때마다 정렬된 부분이 점점 더 커지기 때문에, 검사할 필요가 없는 부분이 늘어납니다.
2. 조기 종료:
   • 플래그를 사용하여 이번 반복에서 교환이 없었다면 배열이 이미 정렬된 상태로 간주하고 반복을 종료합니다.
   • 이는 불필요한 반복을 줄여줍니다.

이 두 가지 최적화는 버블 정렬의 성능을 개선하는 데 도움을 줍니다. 하지만 버블 정렬은 여전히 시간 복잡도가 O(n^2)로, 데이터 양이 많아질 경우 성능이 저하될 수 있습니다. 따라서 큰 데이터 집합을 정렬할 때는 퀵 정렬, 병합 정렬, 힙 정렬 등의 더 효율적인 정렬 알고리즘을 사용하는 것이 좋습니다.

 

최적화 코드

import java.util.Arrays;

public class Main {
    
    public static void main(String[] args) {
        int[] arr = {5, 1, 9, 4, 6, 2, 7, 8, 3, 10};
        
        bubbleSort(arr);
        
        System.out.println(Arrays.toString(arr));
    }
    
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            // 배열이 이미 정렬된 상태인지 확인하는 플래그
            boolean isSorted = true;
            
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 정렬되지 않았으므로 플래그를 false로 설정
                    isSorted = false;
                    swap(arr, j, j + 1);
                }
            }
            
            // 만약 이번 반복에서 교환이 없었다면 배열은 이미 정렬된 상태입니다.
            if (isSorted) {
                // 반복을 종료합니다.
                break;
            }
        }
    }
    
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}