버블정렬

정순동·2024년 2월 15일

버블정렬 알고리즘 정렬

알고리즘

목록 보기

15/33

버블 정렬

버블 정렬은 이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 반복하는 알고리즘이다. 단순 교환 정렬(straight exchange sort)라고도 부른다.

버블 정렬은 정렬시 데이터의 분포가 거품이 올라오는것 처럼 보인다고 해서 버블 정렬이다.

참고로 버블 정렬의 시간 복잡도는 O(n^2)이다.
1만개를 1초에 정렬하면 10만개는 100초정도 필요하다.

버블 정렬 알아보기

	int[] arr = {6,4,3,7,1,9,8};

위와 같은 배열이 있다고 하자, 버블 정렬은 맨 끝 2숫자 9,8 부터 정렬에 들어간다. 오름차순으로 arr배열을 정려한다고 했을때 9가 맨 오른쪽에 와야 하기에 9,8 순서를 바꾼다.

	int[] arr = {6,4,3,7,1,8,9};

그럼 위와 같은 배열로 바뀐다. 그 다음 1과8을 비교한다. 1은 8보다 작기에 교환할 필요가 없다. 그 다음은 7과 1을 비교한다. 7은 1보다 크기에 교환한다. 이런 순서로 배열의 모든 요소를 비교하여 교환을 n-1회 실시합니다. 이렇게 되면 가장 작은 요소가 맨 처음으로 이동하게 된다.

	int[] arr = {1,6,4,3,7,8,9};

위 처럼 정렬되는데 이런 일련의 과정(비교, 교환)을 패스(pass)라고 한다.

이어서 arr[0]을 제외한 나머지 요소로 패스를 수행하고 그 결과 두 요소의 정렬이 끝난 상태가 된다. 패스를 수행 할 때마다 정렬이 끝난 맨끝 요소들은 제외하고 정렬한다. 패스를 k번 수행하면 앞쪽부터 k개의 요소가 정렬된다는 것을 알 수 있다.

※물론 버블정렬은 반대로 수행해도 된다.

수행하는 패스의 횟수가 n - 1번인데 이는 n - 1번의 패스를 수행하고 나면 이미 마지막 요소는 자동으로 정렬이 된 상태가 되어 n번째 패스를 수행 할 필요가 없기 때문이다.

최선의 경우(이미 정렬된) 1번만 돌고 말지만, 나머지의 거의 모든 경우에서 최악의 성능을 보여준다. 그저 만들기 쉽고 직관적인 기본적 정렬인 것이다.

버블 정렬 만들어 보기

public class Bubble {
    static void swap(int[] a, int idx1, int idx2) {
        int tmp = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = tmp;
    }

    // 버블 정렬
    static void bubbleSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            for(int j = a.length - 1; j > i; j--) {
                if (a[j - 1] > a[j]) {
                    swap(a, j - 1, j);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.println("버블 정렬");
        System.out.print("요솟수 : "); int nx = sc.nextInt();
        int[] x = new int[nx];

        for (int i = 0; i  < nx; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = sc.nextInt();
        }

        bubbleSort(x);

        System.out.println("오름차순 정렬 완료");
        for (int i = 0; i < nx; i++)
            System.out.println("x[" + i + "]=" + x[i]);
    }
}

가장 기본적인 버블정렬 방법이다.

bubbleSort의 이중for문의 변수 i는 이미 정렬된 요소의 개수를 뜻한다. 첫 패스는 정렬된 부분이 없으니 0으로 시작, 각 패스가 끝날 때 마다 요소는 앞에서부터 1개씩 정렬되기에 또 비교,대입 할 필요가 없어서 제외한다.

변수j가 비교할 인덱스이다. [j - 1], [j]를 비교하고 [j - 1]요소가 더 크다면 둘의 순서를 swap()메서드를 통해 바꾼다. swap은 tmp라는 변수에 잠시 값을 저장하고 서로 위치를 바꾸는 메서드이다.

j의 값은 i아래로 내려 갈 필요가 없다.(이미 정렬 다 된 부분들) 따라서 2번째 내부for문의 조건식은 'j > i;' 이다.

버블 정렬 개선해 보기

위 코드에서 배열에 6,4,3,7,1,9,8을 정렬 해 보자.

1패스가 끝났을 때 배열 = 1,6,4,3,7,8,9
2패스가 끝났을 때 배열 = 1,3,6,4,7,8,9
3패스가 끝났을 때 배열 = 1,3,4,6,7,8,9 → 정렬이 끝남.
4...

위 코드에서 버블 정렬 패스는 n-1번(여기서는7-1)수행 되는데 4,5,6패스는 이미 정렬이 된 배열을 사실상 하는 일은 없이 비교만 하는 패스가 된다.

이 때, 위에서 설명 했듯 4패스는 요소를0회 교환한다. 이는 더 이상 정렬할 요소가 없다는 뜻으로 정렬 작업을 멈추면 된다.

따라서 버블 정렬 메서드 bubbleSort()부분을 아래처럼 수정 해 보자.

// 버블 정렬
    static void bubbleSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int exchanged = 0; // 패스에서 교환하는 횟수를 저장
            System.out.println("정렬 중인 패스: " + (i + 1));
            for(int j = a.length - 1; j > i; j--) {
                if (a[j - 1] > a[j]) {
                    swap(a, j - 1, j);
                    exchanged++;
                }
            }
            if (exchanged == 0) break; // 교환이 이루어지지 않았기에 멈춘다.
        }
    }

결과는 이전 결과 처럼 똑같겠지만, 정렬 중인 패스(이 코드에서 추가함)부분이 4에서 끝나는 것을 알 수 있다. 이는 4패스 도중 교환(exchanged변수)이 이루어 지지 않았음을 판단 후, break;를 걸어 줬기 때문이다.

버블 정렬 개선해 보기2

새로운 배열 {1,3,9,4,7,8,6}을 버블 정렬해 보자.

1패스가 끝났을 때 배열 = 1,3,4,9,6,7,8
2패스가 끝났을 때 배열 = 1,3,4,6,9,7,8
3패스가 끝났을 때 배열 = 1,3,4,6,7,9,8
4패스가 끝났을 때 배열 = 1,3,4,6,7,8,9 → 정렬 끝
5...

이번 경우에는 우리가 개선할 부분이 뭐가 있을까? 바로 1패스 부분에 나온다.
1패스가 끝나자 마자 1,3,4 부분이 이미 정렬됐다. 이렇게 각 패스에서 비교, 교환을 하다 어떤 시점 이후에 교환하지 않는다면 그보다 앞쪽의 요소는 이미 정렬을 마친 상태라고 생각해도 된다. 따라서 두 번째 패스는 3요소를 제외한 4개만 비교, 교환을 수행하면 된다.

아래는 bubbleSort()의 수정 버전이다.

static void bubbleSort(int[] a) {
        int k = 0;  // a[k]보다 앞쪽은 정렬을 마친 상태
        while(k < a.length - 1) {
            int last = a.length - 1; // 마지막으로 요소를 교환한 위치
            for (int j = a.length - 1; j > k; j--)
                if(a[j - 1] > a[j]) {
                    swap(a, j-1, j);
                    last = j;
                }
            k = last;
        }
    }