[백준] 2750 - 수 정렬하기

👉🏻 백준 2750번 문제 바로가기

❓버블정렬

❗️버블 정렬의 핵심 이론
: 버블정렬은 두 인접한 데이터의 크기를 비교해 정렬하는 방법이다.
간단하게 구현할 순 있지만, 시간 복잡도는 O(n2)으로 다른 정렬 알고리즘보다 속도가 느린 편이다.
루프를 돌면서 인접한 데이터 간의 swap 연산으로 정렬한다.

❗버블 정렬 과정
: 1. 비교 연산이 필요한 루프 범위를 설정한다.
2. 인접한 데이터 값을 비교한다.
3. swap 조건에 부합하면 swap 연산을 수행한다.
4. 루프 범위가 끝날 때까지 2~3을 반복한다.
5. 정렬 영역을 설정한다. 다음 루프를 실행할 때는 이 영역을 제외한다.
6. 비교 대상이 없을 때까지 1~5를 반복한다.

만약, 특정 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬되었다는 뜻이므로
프로세스를 종료한다.

❗️pseudo code

       N (정렬할 수 개수)
        A (정렬할 배열 선언)
        for (i : 0 ~ N -1 - i) {
            for (j : 0 ~ N - 1 - i) {
                현재 A 배열의 값보다 1칸 오른쪽 배열의 값이 더 작으면 두 수 바꾸기
            }
        }
        A 배열 출력
        

✨ solve

import java.util.Scanner;

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 - 1 - i; 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]);
        }
    }
}