[Java] baekjoon 2750번(Bubble Sort)

백준 2750번은 단순한 내림차순 정렬 문제이다.

하지만 문제의 의도가 java의 Arrays.sort 메서드를 이용해 푸는것은 아닌것 같아 찾아 보던중 Bubble Sort 방법에 대해

알아보았습니다.

 

1. Bubble Sort란?

가장 기본적인 정렬방식이므로 이해하기도 어렵지 않다.

• Bubble Sort는 데이터를 '비교'하면서 정렬하기 때문에 '비교 정렬'이다.
• 정렬의 대상이되는 배열 이외의 추가적인 공간이 필요하지 않기 때문에 '제자리 정렬(in-place-sort)'이다.
  (정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 본다)

 

 

2. Bubble Sort의 정렬 방법

bubble sort의 정렬 방법은 순서로 나타내면 다음과 같다.

 

1. 앞에서부터 현재 원소와 바로 다음의 원소를 비교한다.

2. 현재 원소가 다음 원소보다 크면 원소를 교환한다.

3. 다음 원소로 이동하여 해당 원소와 그 다음원소를 비교한다.

 

 

더 이해하기 쉬게 하기 위해 {5, 2, 3, 4, 1}이라는 배열을 예로 나타내면 다음과 같다.

5

2

3

4

1

 

round1

제일 첫번째 인덱스(0, 값은 5)부터 시작한다.

2

5

3

4

1

 

2

3

5

4

1

2

3

4

5

1

2

3

3

1

5

 

round2

2

3

3

1

 

2

3

3

1

 

2

3

1

3

 

round3

2

3

1

 

2

1

3

 

round4

1

2

 

즉, 결과를 놓고보면 매 round마다 제일 큰 수는 가장 오른쪽(마지막 index)에 배치되고 제일 큰수가 마지막에 배치 되었으니 다음 round에서는 배제시켜도 괜찮다는 것이다.

따라서 정리해보면 2개의 반복문이 필요한데,

1. round를 만들어줄 반복문(round의 개수는 배열의 크기 -1개)
2. round 안에서 두수를 비교해 swap여부를 결정(if)하고 swap을 반복해줄 반복문(swap여부는 배열의 크기 - 현재 라운드)

 

코드로 나타내면 다음과 같다.

public class _2750 {
    private static void bubble_sort(int[] a, int size) {

        // round는 배열 크기 - 1 만큼 진행됨 
        for (int i = 1; i < size; i++) {

            // 각 라운드별 비교횟수는 배열 크기의 현재 라운드를 뺀 만큼 비교함
            for (int j = 0; j < size - i; j++) {

                /*
                 *  현재 원소가 다음 원소보다 클 경우
                 *  서로 원소의 위치를 교환한다.
                 */
                if (a[j] > a[j + 1]) {
                    int temp = a[i];
					a[i] = a[j];
					a[j] = temp;
                }
            }
        }
    }

 

답의 전문은 다음과 같다.

import java.util.Scanner;

public class _2750 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            sc.nextLine();
        }
        sc.close();
        
        bubbleSort(arr, arr.length());

        for (int x : arr) {
            System.out.println(x);
        }



    }
    
    private static void bubbleSort(int[] a, int size) {

        // round는 배열 크기 - 1 만큼 진행됨 
        for (int i = 1; i < size; i++) {

            // 각 라운드별 비교횟수는 배열 크기의 현재 라운드를 뺀 만큼 비교함
            for (int j = 0; j < size - i; j++) {

                /*
                 *  현재 원소가 다음 원소보다 클 경우
                 *  서로 원소의 위치를 교환한다.
                 */
                if (a[j] > a[j + 1]) {
                    int temp = a[i];
					a[i] = a[j];
					a[j] = temp;
                }
            }
        }
}

 

## 이렇게 Arrays.sort() 메서드를 사용하지 않고 구현하게 되면 단계별로 풀어보기 - 정렬 카테고리에서 2587번, 25305번을 풀 경우 반복횟수를 줄일 수 있어 좋다.