[정렬] 1. 버블 정렬(Bubble Sort) 알고리즘

정렬 알고리즘의 가장 기초인 버블 정렬에 대해 알아보겠습니다. Java에서 제공되는 Arrays.sort()를 사용해도 되지만, 기본적인 알고리즘은 알아두는 것이 좋을 것 같습니다.

정렬 알고리즘 - 버블 정렬

버블 정렬은 배열에 아래와 같은 순서로 숫자가 들어있다고 할 때,

int[] num = {1,6,4,2,3,5}

이를 오름차순 정렬하기 위해 가장 처음부터 인덱스를 증가시키면서 인접한 두 개의 원소를 비교하면서 정렬합니다.
아래 그림1.에서 청록색 색칠된 칸이 비교대상이 되는 인접한 두 개의 원소이고, 화살표는 비교 결과 앞과 뒤의 값이 교환되는 경우입니다.

그림1. 버블정렬 오름차순 첫 번째 단계

그림 1.처럼 보글보글 거리는 느낌으로 처음부터 끝까지 두 개 원소를 순차적으로 비교하고 교체하는 것을 하나의 단계라고 하면, 주어진 배열에 대해 버블 정렬 첫 번째 단계가 완료될 때, 그림 1.의 마지막 배열의 모습이 됩니다.

그림 1. 을 자세히 보면, 첫 번째 1,6은 비교 결과가 그대로이고, 그 뒤부터 6이 한 칸씩 밀려나게 됩니다.
그 결과 가장 큰 수인 6이 가장 끝까지 이동한 것을 볼 수 있습니다.
오름차순에서 가장 큰 수인 6은 이미 마지막 자리로 이동했으므로 두 번째 단계에서 마지막 자리에 있는 6은 그대로 두고 그 앞자리까지 비교를 하면 됩니다.

그림2. 버블정렬 오름차순 두 번째 단계

그림 2. 에서 두 번째 단계에서 어떻게 원소가 이동하는지 보여주고 있습니다. 4가 한 칸씩 뒤로 밀려서 5 앞에 위치하게 되면서 오름 차순 정렬이 완료되었습니다.
단, 오름 차순 정렬이 끝났지만, 버블 정렬에서는 정렬이 완료되었을 때 알고리즘이 끝나지 않고, 무조건 다음 단계로 이어집니다.

728x90

내림차순도 비슷합니다.

그림3. 버블정렬 내림차순 첫 번째 단계

그림 3. 에서 내림차순 정렬 첫 번째 단계가 수행되고 나면 가장 작은 1이 마지막 자리로 이동합니다.

그림4. 버블정렬 내림차순 두 번째 단계

그림 4. 에서 내림차순 정렬 두 번째 단계가 수행되고 나면 두 번째로 작은 2가 마지막 자리로 이동합니다.

그림5. 버블정렬 내림차순 세 번째 단계

그림 5. 에서 내림차순 정렬 세 번째 단계가 수행되고 나면 세 번째로 작은 3이 마지막 자리로 이동합니다.

그림6.  버블정렬 내림차순 네 번째 단계

그림 6. 에서 내림차순 정렬 네 번째 단계가 수행되고 나면 네 번째로 작은 4가 마지막 자리로 이동합니다.
이후에 내림차순 다섯 번째 단계도 수행되지만, 이미 내림차순 정렬이 완료되어서 자리 이동은 없게 됩니다.

 Java에서 구현한 코드는 다음과 같습니다.  

//#Parameter
//desc: 정렬방법, true이면 오름차순, false이면 내림차순
//num: 정렬대상인 1차원 배열

public class BubbleSort {
    public int[] bubbleSort(boolean desc,int[] num){
        int tmp;
        if(desc){ //오름차순 정렬
            for(int i=0;i<num.length;i++){
                for(int j=0;j<num.length-i-1;j++){
                    if(num[j+1]<num[j]){
                        tmp=num[j];
                        num[j]=num[j+1];
                        num[j+1]=tmp;
                    }
                }
            }
        }else{ //내림차순 정렬
            for(int i=0;i<num.length;i++){
                for(int j=0;j<num.length-i-1;j++){
                    if(num[j+1]>num[j]){
                        tmp=num[j];
                        num[j]=num[j+1];
                        num[j+1]=tmp;
                    }
                }
            }
        }
        return num;
    }
    public static void main(String[] args) {

        int[] num = {1, 6, 4, 2, 3, 5};
        BubbleSort bubble = new BubbleSort();

        for(int n:bubble.bubbleSort(true,num)) System.out.print(" "+n);
        System.out.println();
        for(int n:bubble.bubbleSort(false,num)) System.out.print(" "+n);
    }
}