[코테 알고리즘] 버블(Bubble) 정렬

버블(Bubble) 정렬

---

이웃한 값을 비교해서 더 작은값을 앞으로 보내자
(한번 돌면 가장 큰값이 가장 뒤로 오게 된다, 뒤부터 정렬)

🕑 시간복잡도: O(N^2)
[비교연산 횟수: N-1 + N-2 + N-3 + ... + 1 = (N^2)/2번]

버블(Bubble) 정렬 코드 구현

---

1. 루프loop를 돌면서 이웃한 값 간의 swap연산으로 정렬한다.

<백준 알고리즘, 2750번>

🎯 N이 1000보다 작음으로 시간복잡도가 O(N^2)인 알고리즘을 써도 풀 수 있다.
    (1억번의 연산 = 1초)

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner scannner = new Scanner(System.in);
        int N = scanner.nextInt();
        int A[] = new int[N];
        for(int i = 0; i < N; i++) {
            A[i] = scanner.nextInt();
        }

        for(int i = 0; i < N-1; i++) {
            for(int j = 0; j < N-1-i; j++) {
                if(A[j+1] < A[j]) {
                    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]);
        }
    }
}