백준 2750) 수 정렬하기 + 버블정렬(Bubble Sort)

정렬에 대하여 이론만 아는 것 같아서 하나씩 구현해보기로 했다.

2750) 수 정렬하기 _브론즈2

https://www.acmicpc.net/problem/2750

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

✒️ 내가 푼 과정

버블 정렬은 첫번째 요소부터 끝 요소까지 옆의 요소를 비교하여 정렬한다.
n개의 정수가 있을 때 이 과정은 최대 n번 반복한다.

최대반복 예시 입력

5
5
4
3
2
1

해당 예시 버블정렬 과정

5 4 3 2 1

• 5와 4를 비교 : 5 > 4 이므로 교환 => 4 5 3 2 1
• 5와 3을 비교 : 5 > 3 이므로 교환 => 4 3 5 2 1
• 5와 2를 비교 : 5 > 2 이므로 교환 => 4 3 2 5 1
• 5와 1을 비교 : 5 > 1 이므로 교환 => 4 3 2 1 5

4 3 2 1 5

• 4와 3을 비교 : 4 > 3 이므로 교환 => 3 4 2 1 5
• 4와 2를 비교 : 4 > 2 이므로 교환 => 3 2 4 1 5
• 4와 1을 비교 : 4 > 1 이므로 교환 => 3 2 1 4 5
• 4와 5를 비교 : 4 < 5 이므로 교환X => 3 2 1 4 5

3 2 1 4 5

• 3과 2를 비교 : 3 > 2 이므로 교환 => 2 3 1 4 5
• 3과 1을 비교 : 3 > 1 이므로 교환 => 2 1 3 4 5
• 3과 4를 비교 : 3 < 4 이므로 교환X => 2 1 3 4 5
• 4과 5를 비교 : 4 < 5 이므로 교환X => 2 1 3 4 5

2 1 3 4 5

• 2와 1을 비교 : 2 > 1 이므로 교환 => 1 2 3 4 5
• 2와 3을 비교 : 2 < 3 이므로 교환X => 1 2 3 4 5
• 3과 4를 비교 : 3 < 4 이므로 교환X => 1 2 3 4 5
• 4와 5를 비교 : 4 < 5 이므로 교환X => 1 2 3 4 5

1 2 3 4 5

• 정렬 완료

일반반복 예시 입력

5
5
4
1
3
2

해당 예시 버블정렬 과정

5 4 1 3 2

• 5와 4를 비교 : 5 > 4 이므로 교환 => 4 5 1 3 2
• 5와 1을 비교 : 5 > 1 이므로 교환 => 4 1 5 3 2
• 5와 3을 비교 : 5 > 3 이므로 교환 => 4 1 3 5 2
• 5와 2를 비교 : 5 > 2 이므로 교환 => 4 1 3 2 5

4 1 3 2 5

• 4와 1을 비교 : 4 > 1 이므로 교환 => 1 4 3 2 5
• 4와 3을 비교 : 4 > 3 이므로 교환 => 1 3 4 2 5
• 4와 2를 비교 : 4 > 2 이므로 교환 => 1 3 2 4 5
• 4와 5을 비교 : 4 < 5 이므로 교환X => 1 3 2 4 5

1 3 2 4 5

• 1과 3을 비교 : 1 < 3 이므로 교환X => 1 3 2 4 5
• 3과 2를 비교 : 3 > 2 이므로 교환 => 1 2 3 4 5
• 3과 4를 비교 : 3 < 4 이므로 교환X => 1 2 3 4 5
• 4와 5를 비교 : 4 < 5 이므로 교환X => 1 2 3 4 5

1 2 3 4 5

• 정렬 완료

코드 작성

n개의 수가 있을 때, 옆 요소와 n-1번 비교 하는 과정을 최대 n번 반복한다.
이것을 2중 반복문으로 풀어냈다.
지금 생각해보면 왜 n번 반복한다고 생각했는지 의문,,

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 수 입력 받기
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        // 버블정렬 (Bubble Sort)
        for(int i=0; i<n; i++) {
            for(int j=0; j<n-1; j++) {
            	// 오른쪽 요소의 값이 더 크다면 교환
                if (arr[j] > arr[j+1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
        
        // 출력
        for(int i=0; i<n; i++) {
            System.out.println(arr[i]);
        }
        br.close();
    }
}

✒️ 피드백 (chatGPT)

문제와 내 코드를 올려주니 아래와 같은 피드백을 받았다.
그런데 성능차이는 별로 없었음..

1. 불필요한 연산

i는 n-1까지 반복되는 것임. (나는 i가 n까지 반복되게함)
ex) 5개의 수는 4번의 과정을 거치면 버블정렬 결과가 나옴.
j는 n-1-i까지 반복되는 것임. (나는 j가 n-1까지 반복되게함)
ex) 5개의 수는 최악의 상황일 때 거듭할 수록 비교를 1번씩 적게 하기 때문에 -i를 추가해야함.

2. 정렬이 이미 완료된 이후에도 계속 실행

i의 반복문은 n-1까지 반복되지만 이는 최악의 상황이고 그 전에 정렬이 끝날 수도 있음.
그렇다면 이미 정렬이 된 상태에서 불필요한 비교가 발생.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        // 버블정렬 (Bubble Sort) 최적화
        for(int i=0; i<n-1; i++) {
            boolean swapped = false; // 교환 발생 여부 확인
            
            for(int j=0; j<n-1-i; j++) {
                if (arr[j] > arr[j+1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                    swapped = true; // 교환 발생 시
                }
            }
            
            if (!swapped) break; // 교환 없을 시 반복문 조기 종료
        }
        
        for(int i=0; i<n; i++) {
            System.out.println(arr[i]);
        }
        br.close();
    }
}