[JAVA][백준][B2] 수 정렬하기

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

 

📒 문제

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

 

● 시간 제한 / 메모리 제한

 1 초 /  128 MB 

입력

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

출력

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

 

입출력 예

# 입력1
5
5
2
3
4
1

# 출력1
1
2
3
4
5

 

알고리즘 분류

• 구현
• 정렬

---

💻 소스코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 풀이 시작
        int N = Integer.parseInt(br.readLine()); // 수의 개수

        int[] arr = new int[N];
        for(int i = 0 ; i < arr.length; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        // 버블 정렬(Bubble Sort)
        for(int i = 0; i < arr.length; i++){
            for(int j = 0 ; j < arr.length -i-1; j++) {
                if(arr[j] > arr[j+1]){
                    int n = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = n;
                }
            }
        }
        for(int n : arr) bw.write(n+"\n");

        bw.flush();
        bw.close();
    }
}

 

📝 풀이

sort() 함수를 이용하면 쉽게 해결할 수 있다.

 

하지만 버블 정렬을 직접 구현 해보기 위해 정렬을 직접 구현해봤다.

해당 문제는 N이 1,000보다 작기 때문에 버블 정렬의 시간 복잡도 O(n²)를 가져도 문제를 해결할 수 있다.

 

버블 정렬은 인접 요소를 비교해 swap 연산을 수행하는 정렬이다.

정렬 하면 뒤쪽엔 정렬된 요소들이 쌓이기 때문에 반복문을 수행할 때 반복문 크기를 N -i -1을 해주었다.

 

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