[Algorithm] 버블 정렬(Bubble sort)

 

버블 정렬 기본 개념

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘(인접한 2개의 레코드를 비교하여 크기를 순서에 맞게 서로 교환한다.)
선택 정렬과 기본 개념이 유사하다.

버블 정렬 구체적인 개념

버블 정렬은 1|2, 2|3, 3|4 ... 이런 식으로 마지막(마지막 -1) 번째 자료까지 비교하여 교환한다.
1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 2번째 자료는 정렬에서 제외된다. 이런 식으로 정렬을 1회전 수행할 때마다 정렬에서 제외되는 자료가 하나씩 늘어난다.

버블 정렬 알고리즘 예제

import java.util.Arrays;

public class BubbleSort {

    public static void main(String[] args) {
        
        int[] unsortedArray = {9, 2, 6, 3, 4};
        System.out.println("Array Before sorting: " + Arrays.toString(unsortedArray));
        System.out.println("Array After sorting : " + Arrays.toString(bubbleSort(unsortedArray)));
    }
    
    private static int[] bubbleSort(int[] arr) {
        
        int temp = 0;
        int arrLength = arr.length;
        
        for (int i=0; i<arrLength; i++) {
            for (int j=1; j<arrLength-i; j++) {
                if (arr[j-1] > arr[j]) {
                    temp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                }
            }
            System.out.println((i+1) + "th element swapped : " + Arrays.toString(arr));
        }
        return arr;
    }
}

버블 정렬 알고리즘 특징

장점
구현이 매우 간단하다.

단점
배열에서 모든 다른 요소들과 비교하고 교환해야 한다. 일반적으로 교환 작업(SWAP)이 이동 작업(MOVE) 보다 더 복잡하기 때문에 버블 정렬은 단순성에서도 불구하고 거의 쓰이지 않는다.

 

단순하지만 비효율적인 방법
- 버블 정렬, 선택 정렬, 삽입정렬

복잡하지만 효율적인 방법
- 셸 정렬, 힙 정렬, 퀵 정렬, 병합 정렬

 

정렬 알고리즘 Post

[프로그래밍/Algorithm] - [Algorithm] 버블 정렬(Bubble sort)

[프로그래밍/Algorithm] - [Algorithm] 삽입 정렬(Insertion sort)

[프로그래밍/Algorithm] - [Algorithm] 선택 정렬(Selection sort)

[프로그래밍/Algorithm] - [Algorithm] 셸 정렬(Shell sort)