[백준] 수 정렬하기(버블 정렬 사용)

---

백준 온라인 저지 2750번 - 수 정렬하기

간단한 수 정렬문제를 공부했던 버블 정렬 알고리즘을 통해 해결해보았다.

문제의 시간 제한(2초)과 데이터의 크기(1 ≤ N ≤ 1000)를 보니 버블 정렬의 시간 복잡도(n^2)로 계산해 보았을 때 1000 * 1000 = 1000000으로 효율적이지는 않겠지만 충분히 버블 정렬을 통해 해결할 수 있을 것 같았다.

지켜야 할 키 포인트는 아래와 같다!

1. 버블 정렬의 핵심은 loop내에서 인접 데이터 간의 swap 연산
2. 만약 특정 루프의 전체 영역에서 swap이 발생하지 않았다면, 그 영역 뒤에 있는 데이터가 모두 정렬되었다는 뜻이므로 프로세스를 종료

BubbleSort.java

package com.example.Etc;

/**
 * 백준 온라인 저지 2750 - 수 정렬하기
 */
public class BubbleSort {
    public int[] sortAsc(int[] target) {
        int len = target.length;
        for(int i = 0; i < len - 1; i++) {
            boolean isSwaped = false;
            for(int j = 0; j < len - 1 - i; j++) {
                if(target[j] > target[j + 1]) {
                    int temp = target[j];
                    target[j] = target[j + 1];
                    target[j + 1] = temp;
                    isSwaped = true;
                }
            }
            // 한 번의 라운드 동안 위치가 변경된 적이 없다면 이미 정렬이 되어있으므로 프로세스 종료
            if(isSwaped == false) {
                break;
            }
        }
        return target;
    }
}

BubbleSortTest.java

package com.example.Etc;

import static org.junit.Assert.assertArrayEquals;

import org.junit.Test;

public class BubbleSortTest {
    @Test
    public void bubbleSortTest() {

        BubbleSort sort = new BubbleSort();

        // 정렬이 안되어 있는 경우
        int[] target1 = {5, 2, 3, 4, 1};
        int[] result1 = sort.sortAsc(target1);

        // 정렬이 되어 있는 경우
        int[] target2 = {1, 2, 3, 4, 5};
        int[] result2 = sort.sortAsc(target2);

        int[] expected = {1, 2, 3, 4, 5};

        assertArrayEquals(expected, result1);
        assertArrayEquals(expected, result2);
    }
}