[Java] 버블 정렬

버블 정렬

• 앞 뒤의 수를 확인해 오른쪽으로 순차적으로 이동하며 배열의 값을 크기대로 정렬한다.
• N개의 인덱스가 존재하는 배열일 경우 N개를 N번씩 돌아가며 정렬해야하므로 N^2의 시간복잡도를 가지게 된다.

---

문제

• 백준 2750

오름차순 정렬하여 출력한다.

• 풀이

첫 번째는 버블 정렬, 두 번째는 우선순위 큐를 이용하여 풀었다.

1️⃣ 버블 정렬

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(bf.readLine());
        }

        for (int i = 0; i < N-1; i++) {
            for (int j = 0; j < N - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }

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

2️⃣ 우선순위 큐

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        for (int i = 0; i < N; i++) {
            queue.add(Integer.parseInt(bf.readLine()));
        }
        
        while (!queue.isEmpty()) {
            System.out.print(queue.poll() + " ");
        }
    }
}