[JAVA] 버블 정렬 (Bubble Sort)

2021. 11. 2. 15:15

버블 정렬 (Bubble Sort)

가장 단순한 정렬 알고리즘
인접한 요소와 정렬 기준(오름차순, 내림차순)대로 교환
안정 정렬 (stable sort)
: 정렬 후에도 같은 값들 끼리의 순서가 보장됨을 의미
제자리 정렬 (in-place sort)
: 데이터에 필요한 공간을 제외하고 추가적인 공간이 필요없음을 의미
정렬한 데이터의 개수가 적을때는 나쁘지 않은 속도를 보임

버블 정렬 방법 (오름차순 기준)

첫 번째 사이클이 끝나면 맨 마지막 값이 정렬되고, 두 번째 사이클이 끝나면 뒤에서 두 번째의 값이 정렬된다. 이같은 과정을 계속 반복하면 최종적으로 정렬이 된다.

버블 정렬의 성능

시간복잡도
최악의 경우 : O(n^2)
최선의 경우 : O(n)
최악의 경우 : 모든 데이터가 역순인 경우 (5, 4, 3, 2, 1)
5를 정렬하기 위해서는 n-1번 비교 및 교환해야하고, 4를 정렬하기 위해서는 n-2번 비교 및 교환해야 한다.
즉, 5를 정렬할 때 4번, 4를 정렬할 때 3번, 3을 정렬할 때 2번, 1과 2를 정렬할 때 1번의 비교 및 교환을 거치게 되므로 비교 횟수는 4 + 3 + 2 + 1회가 된다.
따라서, 데이터가 n개일 때 총 비교횟수는 (n-1) + (n-2) + (n-3) + ... + 2 + 1 이 되므로 등차수열의 합에 따라 1/2n(n-1)이 되며 빅-오는 최고차항을 가지기 때문에 O(n^2)이 된다.
최선의 경우 : 모든 데이터가 이미 정렬된 경우 (1, 2, 3, 4, 5)
한 번도 교환이 이루어지지 않았다면 이미 정렬된 상태이므로 n번 비교 후 반환되어 O(n) 이 된다.

기본 구현

기본 int형 배열 정렬 구현
[BubbleBasic.java]

package Sort.Bubble;

/**
 * 단순히 int형 배열만 오름차순 또는 내림차순으로 정렬하는 경우
 */
public class BubbleBasic {
    private boolean isDescending = false;

    /**
     * @param arr int형 배열
     * @param isDescending 내림차순 및 오름차순 선택
     */
    public static void sort(int[] arr, boolean isDescending) {
        // 이미 정렬이 되어있는지 확인하기 위한 변수
        boolean isAlreadySorted = true;
        int n = arr.length;

        // 정렬할 값을 선택하는 반복문
        for(int i=0; i<n-1; i++) {
            // 정렬할 값과 나머지 값들을 비교하기 위한 반복문
            // 이미 정렬이 완료된 데이터는 비교대상에서 제외해야 하므로 n-i-1
            for(int j=0; j<n-i-1; j++) {
                // 정렬되지 않았다면
                if (!isSortTwoElements(arr[j], arr[j + 1], isDescending)) {
                    // 데이터를 교환한다.
                    swap(arr, j, j + 1);
                    // 스왑을 했다면 초기 배열 상태가 정렬되지 않았다는 것이므로 false로 변경
                    isAlreadySorted = false;
                }
            }

            // 한 번도 교환이 발생하지 않았다면 이미 정렬된 데이터이므로 반복문을 빠져나온다.
            if (isAlreadySorted) {
                break;
            }
        }
    }

    /**
     *
     * @param arr 데이터 배열
     * @param idx1 교환할 인덱스
     * @param idx2 교환할 인덱스
     */
    private static void swap(int[] arr, int idx1, int idx2) {
        int tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }

    /**
     *
     * @param cmp1 비교할 값
     * @param cmp2 비교할 값
     * @param isDescending 내림차순 및 오름차순 선택
     * @return 내림차순의 경우 cmp1이 작을 경우 false, 그렇지 않으면 true
     *         오름차순의 경우 cmp1이 작을 경우 true, 그렇지 않으면 false
     */
    private static boolean isSortTwoElements(int cmp1, int cmp2, boolean isDescending) {
        // 내림차순일 경우
        if (isDescending) {
            if (cmp1 < cmp2) {
                return false;
            }
            else {
                return true;
            }
        }
        // 오름차순일 경우
        else {
            if (cmp1 < cmp2) {
                return true;
            }
            else {
                return false;
            }
        }
    }
}

BubbleBasic.java 테스트 및 실행시간 측정

package Sort.Bubble;

public class BubbleBasicMain {
    private static final int MAX_COUNT = 10;

    public static void main(String[] args) {
        int[] arr = new int[MAX_COUNT];
        for(int i=0; i<MAX_COUNT; i++) {
            // 0 ~ MAX_COUNT 범위내의 난수를 생성
            arr[i] = (int)(Math.random() * MAX_COUNT);
        }

        // 배열은 참조형 이므로 arr을 넘길 경우 arr값이 변경되기 때문에 복사본을 생성한 후 테스트
        int[] ascArrTest = arr.clone();
        System.out.println("정렬 전 데이터");
        for(int i : ascArrTest) {
            System.out.println(i);
        }
        System.out.println();

        BubbleBasic.sort(ascArrTest, false);
        System.out.println("오름차순 정렬 후 데이터");
        for(int i : ascArrTest) {
            System.out.println(i);
        }
        System.out.println();

        int[] descArrTest = arr.clone();
        BubbleBasic.sort(descArrTest, true);
        System.out.println("내림차순 정렬 후 데이터");
        for(int i : descArrTest) {
            System.out.println(i);
        }

        // 시간복잡도 측정 (오름차순 기준)
        long start = 0;
        long end = 0;

        int[] bestTimeComplexityArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        start = System.nanoTime();
        BubbleBasic.sort(bestTimeComplexityArray, false);
        end = System.nanoTime();
        System.out.println("최선의 경우 오름차순 시간 : " + (end - start) + "ns");

        int[] worstTimeComplexityArray = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        start = System.nanoTime();
        BubbleBasic.sort(worstTimeComplexityArray, false);
        end = System.nanoTime();
        System.out.println("최악의 경우 오름차순 시간 : " + (end - start) + "ns");
    }
}

결과

정렬 전 데이터
2
6
1
7
7
6
0
6
1
0

오름차순 정렬 후 데이터
0
0
1
1
2
6
6
6
7
7

내림차순 정렬 후 데이터
7
7
6
6
6
2
1
1
0
0
최선의 경우 오름차순 시간 : 3805ns
최악의 경우 오름차순 시간 : 18532ns

클래스 비교를 위한 구현

클래스의 특정 값을 이용한 정렬 코드 구현
[BubbleAdvanced.java]

package Sort.Bubble;

import java.util.Comparator;

public class BubbleAdvanced {
    public static <T> void sort(T[] arr) {
        Comparable<? super T> comp;
        boolean isAlreadySorted = true;
        int n = arr.length;

        for(int i=0; i<n-1; i++) {
            for(int j=0; j<n-i-1; j++) {
                comp = (Comparable<? super T>)arr[j];
                if (comp.compareTo(arr[j + 1]) > 0) {
                    swap(arr, j, j + 1);
                    isAlreadySorted = false;
                }
            }

            if (isAlreadySorted){
                break;
            }
        }
    }

    /**
     *
     * @param arr 데이터 배열
     * @param idx1 교환할 인덱스
     * @param idx2 교환할 인덱스
     */
    private static <T> void swap(T[] arr, int idx1, int idx2) {
        T tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }

    public static <T> void sort(T[] arr, Comparator<? super T> comparator) {
        boolean isAlreadySorted = true;
        int n = arr.length;

        for(int i=0; i<n-1; i++) {
            for(int j=0; j<n-i-1; j++) {
                if (comparator.compare(arr[j], arr[j + 1]) > 0) {
                    swap(arr, j, j + 1);
                    isAlreadySorted = false;
                }
            }

            if (isAlreadySorted){
                break;
            }
        }
    }
}

BubbleAdvanced 테스트

package Sort.Bubble;

import java.util.Comparator;

public class BubbleAdvancedMain {
    private static final int MAX_COUNT = 10;

    public static void main(String[] args) {
        Integer[] arr = new Integer[MAX_COUNT];
        for (int i = 0; i < MAX_COUNT; i++) {
            // 0 ~ MAX_COUNT 범위내의 난수를 생성
            arr[i] = (int) (Math.random() * MAX_COUNT);
        }

        // 배열은 참조형 이므로 arr을 넘길 경우 arr값이 변경되기 때문에 복사본을 생성한 후 테스트
        Integer[] ascArrTest = arr.clone();
        System.out.println("정렬 전 데이터");
        for (int i : ascArrTest) {
            System.out.println(i);
        }
        System.out.println();

        BubbleAdvanced.sort(ascArrTest);
        System.out.println("오름차순 정렬 후 데이터");
        for (int i : ascArrTest) {
            System.out.println(i);
        }
        System.out.println();

        Integer[] descArrTest = arr.clone();
        System.out.println("내림차순 정렬 후 데이터");
        BubbleAdvanced.sort(descArrTest, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if (o1 < o2) {
                    return 1;
                } else if (o1 == o2) {
                    return 0;
                } else {
                    return -1;
                }
            }
        });
        for (int i : descArrTest) {
            System.out.println(i);
        }
        System.out.println();

        // 클래스의 특정값을 이용한 정렬 가능
        class Student {
            String name;
            int age;

            public Student(String name, int age) {
                this.name = name;
                this.age = age;
            }

            @Override
            public String toString() {
                return "name='" + name + '\'' +
                        ", age=" + age;
            }
        }

        System.out.println("클래스 정렬 전 데이터");
        Student[] students = new Student[5];
        students[0] = new Student("아이언맨", 11);
        students[1] = new Student("헐크", 4);
        students[2] = new Student("토르", 15);
        students[3] = new Student("블랙위도우", 13);
        students[4] = new Student("캡틴", 4);
        for(Student student : students) {
            System.out.println(student.toString());
        }
        System.out.println();

        System.out.println("클래스 정렬 후 데이터");
        BubbleAdvanced.sort(students, new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                if (o1.age < o2.age) {
                    return -1;
                }
                else if (o1.age == o2.age) {
                    return 0;
                }
                else {
                    return 1;
                }
            }
        });

        for(Student student : students) {
            System.out.println(student.toString());
        }
    }
}

결과

정렬 전 데이터
7
0
0
9
4
4
6
0
5
0

오름차순 정렬 후 데이터
0
0
0
0
4
4
5
6
7
9

내림차순 정렬 후 데이터
9
7
6
5
4
4
0
0
0
0

클래스 정렬 전 데이터
name='아이언맨', age=11
name='헐크', age=4
name='토르', age=15
name='블랙위도우', age=13
name='캡틴', age=4

클래스 정렬 후 데이터
name='헐크', age=4
name='캡틴', age=4
name='아이언맨', age=11
name='블랙위도우', age=13
name='토르', age=15

'0x20. 알고리즘 > 0x21. 이론' 카테고리의 다른 글

[JAVA] 삽입 정렬 (Insertion Sort) (0)	2021.11.04
[JAVA] 선택 정렬 (Selection Sort) (0)	2021.11.03
깊이 우선 탐색 (DFS, Depth-First Search) (0)	2021.10.08
순열(Permutation) 구하기 (0)	2021.10.06
그리디(Greedy) 알고리즘 (탐욕 알고리즘) (0)	2021.10.05

개발자로 살아남기