버블 정렬

Array.sort() 이용하면 쉽게 풀 수 있지만 버블 정렬을 연습하자.

버블 정렬은 시간 복잡도가 O(n^2)로 느리지만 문제의 N이 1000까지라 무리없이 풀 수 있다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }
        
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < N - i - 1; j++) {
                if (A[j] > A[j + 1]) {
                    int temp = A[j];
                    A[j] = A[j + 1];
                    A[j + 1] = temp;
                }
            }
        }
        for (int i = 0; i < N; i++) {
            System.out.println(A[i]);
        }
    }
}

버블 정렬은 최대값을 일일이 찾아서 오른쪽으로 밀어주는 과정을 반복한다.
그러면 처음엔 가장 최댓값, 두 번째는 두 번째로 큰 값, ... 이런식으로 일일이 배열의 오른쪽으로 큰 값들을 루프마다 하나씩 밀어버린다. 그러면 이중 루프를 돌리면 숫자가 오름차순으로 밀리게 된다.

만약 내림차순으로 정렬하고 싶다면 숫자 바꾸는 조건만 간단히 바꾸면 된다.