정렬 - 버블 정렬 (Bubble Sort)

#1 알고리즘

#1-1

정렬 방식이 마치 거품이 수중에 있다가 수면 위로 보글보글 올라가는 모습과 비슷해서 버블 정렬이라고 이름 붙여졌다. 기본적인 버블 정렬은, 정렬 작업을 시작할 때 중간에 배열 이미 정렬된 상태여도 maxIndex가 1이 되는 마지막 반복까지 무의미한 순환을 계속한다. 이 문제점을 해결하기 위해 알고리즘에 한 가지 장치를 할 수 있는데, 그걸 향상된 버블 정렬이라고 부른다.

 

#2-1

반드시 n * (n - 1) / 2번의 비교를 하는 일반 버블 정렬에 비해, 향상된 버블 정렬은 비교 횟수를 최소 (n - 1)번까지 낮출 수 있다.

 

#2 코드

#2-1 자바

public static void bubbleSort(int[] array, int startIndex, int endIndex) {
    
    for(int maxIndex = endIndex; startIndex < maxIndex; maxIndex--) {
        boolean isSorted = true;
        
        // 배열의 0 ~ (maxIndex - 1)번째 원소를 순회한다 
        for(int i = 0; i < maxIndex; i++) {
            
            //해당 원소가 바로 오른쪽 원소보다 크면 값을 서로 교환한다 
            if(array[i + 1] < array[i]) {                    
                int temp = array[i + 1];
                array[i + 1] = array[i];
                array[i] = temp;
                
                isSorted = false;
            }
        }
        
        // 교환이 한번도 일어나지 않았다면 정렬 작업을 종료한다
        if(isSorted) {
            break;
        }
    }
}

 

#2-2 코틀린

fun bubbleSort(array: Array<Int>, startIndex : Int, endIndex : Int) {

    for(maxIndex : Int in endIndex downTo (startIndex + 1)) {
        var isSorted = true

        // 배열의 0 ~ (maxIndex - 1)번째 원소를 순회한다
        for(i : Int in 0..(maxIndex - 1)) {

            // 해당 원소가 바로 오른쪽 원소보다 크면 값을 서로 교환한다
            if(array[i + 1] < array[i]) {
                val temp = array[i + 1]
                array[i + 1] = array[i]
                array[i] = temp

                isSorted = false
            }
        }

        // 교환이 한번도 일어나지 않았다면 정렬 작업을 종료한다
        if(isSorted) {
            break
        }
    }
}

 

#3 요약

버블 정렬은 물 속의 '거품'처럼 인덱스를 올라가면서, 필요하면 값을 교환하는 정렬이다

 

#4 이 개념이 사용된 글

2750 - 수 정렬하기