자바로 구현한 버블 정렬(거품 정렬) 알고리즘

버블 정렬은 두개의 인접한 원소를 비교하는 형식의 정렬방식입니다.

버블 정렬의 특징으로는 1. 비교 정렬입니다. 2. 제자리 정렬입니다. 3. 안정 정렬입니다.

 

1. 비교 정렬 : 서로 값을 비교하여 정렬하는 알고리즘입니다.

2. 제자리 정렬 : 해당 배열 외에 또 다른 배열의 저장 공간이 필요가 없습니다.

3. 안정정렬 : 같은 값일 경우 해당 정렬이 변경되지 않습니다.

 

버블정렬 과정을 요약하면 다음과 같습니다.

1. 처음 원소부터 차례대로 인접한 원소를 비교하고 교환한다.

2. 마지막 원소를 1번을 반복하면서 저장한다.

3. 모든 원소가 저장되거나 교환이 없다면 정렬이 종료된다.

 

그림으로 보겠습니다.

---

---

 

그림으로 보면 크게 어려움 없이 알고리즘 이해가 될것입니다.

 

그럼 자바로 구현해보겠습니다.

 

전체코드

public class Bubble_sort {
    public static void main(String[] args) {
        int[] array = new int[10];

        //배열에 난수 저장
        for(int i=0; i<array.length; i++){
            array[i] = (int)(Math.random()*100);
        }

        //정렬전 배열
        for(int i=0; i<array.length; i++){
            System.out.printf("%d ",array[i]);
            if((i+1)%10 == 0){
                System.out.println();
            }
        }

        //거픔 정렬
        bubble_sort(array);

        System.out.println();
        System.out.println();

        //정렬후 배열
        for(int i=0; i<array.length; i++){
            System.out.printf("%d ",array[i]);
            if((i+1)%10 == 0){
                System.out.println();
            }
        }
    }

    public static void bubble_sort(int[] array){
        /*
        * 시작을 i로 1기준을 잡는다.
        * i는 저장한 원소를 비교하지 않게 하는 역할을 한다.
        */
        for(int i=1; i<array.length; i++){
            boolean flag = false;//교환이 이루어진지 확인하는 변수
            //저장한 원소를 제외하고 첫 원소부터 차례대로 비교한다.
            for(int j=0; j<array.length-i; j++){
                //비교한 후 교환
                if(array[j] > array[j+1]){
                    swap(array,j,j+1);
                    flag = true;//교환이 아루어짐
                }
            }

            //교환이 이루어지지 않았다면 반복 종료
            if(flag == false){
                break;
            }
        }
    }

    public static void swap(int[] array, int i, int min){
        int temp = array[i];
        array[i] = array[min];
        array[min] = temp;
    }

}

 

알고리즘에 해당하는 함수를 보겠습니다.

public static void bubble_sort(int[] array){
    /*
    * 시작을 i로 1기준을 잡는다.
    * i는 저장한 원소를 비교하지 않게 하는 역할을 한다.
    */
    for(int i=1; i<array.length; i++){
        boolean flag = false;//교환이 이루어진지 확인하는 변수
        //저장한 원소를 제외하고 첫 원소부터 차례대로 비교한다.
        for(int j=0; j<array.length-i; j++){
            //비교한 후 교환
            if(array[j] > array[j+1]){
                swap(array,j,j+1);
                flag = true;//교환이 아루어짐
            }
        }

        //교환이 이루어지지 않았다면 반복 종료
        if(flag == false){
            break;
        }
    }
}

이중 for문을 사용해 구현했습니다. 이 구현에 KEY는 저장한 원소는 비교하지 않는 것입니다.

저장한 원소는 round 수 즉 한번 쭉 교환을 끝낸 수와 개수가 같습니다.

즉, round1은 저장 값이 1개 round2는 저장 값이 2개 인것이죠.

그래서 한번 반복하면 i를 증가하면서 저장 개수를 늘려가면 되는 것입니다.

j+1과 j를 비교하기 때문에 i를 처음부터 1로 설정하였습니다.

 

결과 값

 

장점

1. 메모리가 추가적인 소비가 적다.

2. 구현이 매우 쉽다.

3. 안전정렬이 가능하다.

 

단점

1. 다른 알고리즘에 비해 교환 과정이 많아 많은 시간을 소비한다.