Sorting Algorithms - 버블 정렬(Bubble Sort)

1. 정의

버블 정렬(Bubble Sort)에 대해 알아보도록 한다.

버블 정렬이란, 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하는 정렬 알고리즘을 뜻한다. 인접한 2가지 요소의 대소 관계를 검사하여 원하는 순서대로 되어 있지 않은 경우 교환을 하는 것이다. 오름차순, 내림차순으로 정렬할 수 있다.

설명은 이 정도로 하고, 바로 코드로 보도록 한다.

2. 오름차순 정렬

먼저, 오름차순 정렬이다.

public class Main {
 
    public static void main(String[] args) {
 
        int array[] = {122, 16, 5, 3, 9, 8, 56, 124, 98, 102, 115, 1, 17};
        Bubble_Sort_Ascend(array);
    }
 
    public static void Bubble_Sort_Ascend(int[] A) {
 
        int temp;
        for(int i = 0; i < A.length; i++)
            for(int j = 1; j < A.length; j++)
                if(A[j] < A[j - 1]) { // 앞의 요소(A[j - 1])가 뒤의 요소(A[j])보다 큰 경우 ==> 오름차순 정렬이므로 순서를 바꿔 준다.
                    temp = A[j - 1];
                    A[j - 1] = A[j];
                    A[j] = temp;
                }
 
        System.out.print("정렬 결과입니다 : ");
        for(int k = 0; k < A.length; k++)
            System.out.print(A[k] + " ");
    }
}

정렬 결과입니다 : 1 3 5 8 9 16 17 56 98 102 115 122 124

결과는 위와 같다.

오름차순 정렬이므로 배열에서 j 번째 요소와 j - 1 번째 요소를 비교했을 때, j - 1 번째 요소가 j 번째 요소보다 더 크다면 서로 위치를 바꿔주어야 한다.

따라서, Bubble_Sort_Ascend 메소드에서 정수형 변수 temp를 활용하여 j 번째 요소와 j - 1 번째 요소의 위치를 바꿔 주었다.

3. 내림차순 정렬

바로 내림차순 정렬을 보도록 한다.

public class Main {
 
    public static void main(String[] args) {
 
        int array[] = {122, 16, 5, 3, 9, 8, 56, 124, 98, 102, 115, 1, 17};
        Bubble_Sort_Descend(array);
    }
 
    public static void Bubble_Sort_Descend(int[] B) { // 내림차순
 
        int temp;
        for(int i = 0; i < B.length; i++)
            for(int j = 1; j < B.length; j++)
                if(B[j] > B[j - 1]) { // 뒤의 요소(B[j])가 앞의 요소(B[j - 1])보다 큰 경우 ==> 내림차순 정렬이므로 순서를 바꿔 준다.
                    temp = B[j - 1];
                    B[j - 1] = B[j];
                    B[j] = temp;
                }
 
        System.out.print("정렬 결과입니다 : ");
        for(int k = 0; k < B.length; k++)
            System.out.print(B[k] + " ");
    }
}

정렬 결과입니다 : 124 122 115 102 98 56 17 16 9 8 5 3 1 

결과는 위와 같다.

내림차순이라고 해서 오름차순과 크게 다르지 않다. 반복문의 생김새는 바꿀 수 있겠으나, 개인적으로는 저 방식이 가장 간단해 보인다. 그리고 나서 조건문 내부 조건의 부등호만 바꾸면 되는 것이다.

내림차순 정렬이므로, j 번째 요소와 j - 1 번째 요소와의 대소 비교에서 j 번째 요소가 j - 1 번째 요소보다 더 크다면, j 번째 요소와 j - 1 번째 요소의 위치를 바꿔주면 된다.

이상 버블 정렬을 자바로 구현해 보았다.