[do it 알고리즘] 백준 2750 (버블 정렬)

문제 설명

 

풀기 전 생각

• 버블 정렬은 O(N^2)의 시간복잡도를 가짐
• 전체 round는 (배열크기 - 1)만큼 진행
• 각 round에서 비교 횟수는 (배열 크기 -1 - 현재 round)
• 이유는, round가 지날수록 뒤쪽부터 이미 정렬돼 있는 상태이기 때문

코드

import java.util.Scanner;

public class Baek2750 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];

        for(int i = 0; i < N ; i++){
            arr[i] = sc.nextInt();
        }

        for(int i = 0; i < N-1; i++){
            for(int j = 0; j < N-1-i; j++){
                if(arr[j] > arr[j+1]){
                    swap(j,j+1,arr);
                }
            }
        }
        for(int i=0;i<N;i++){
            System.out.println(arr[i]);;
        }
    }
    public static void swap(int a,int b,int[] arr){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

리뷰

구현이 쉬운 만큼 오래 걸린다.
(N-1-i)만 잘 기억하자.