# 백준BOJ/Java/Python : 2750번 수 정렬하기

- Author: @laetipark
- Published: 2022-10-08
- Updated: 2023-05-23
- Source: http://blex.me/@laetipark/%EB%B0%B1%EC%A4%80bojjavapython-2750%EB%B2%88-%EC%88%98-%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0
- Tags: python, algorithm, 백준, java, boj, baekjoon, quicksort

---

[2750번 : 수 정렬하기 원본](https://www.acmicpc.net/problem/2750)

### 알고리즘 분류
- 정렬

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

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

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

### 풀이

- Arrays.sort() 함수 [Java]
    -  Dual-Pivot Quick Sort 방식을 이용하는 정렬 함수이다.

Dual-Pivot Quick Sort 방식은 Quick Sort(퀵 정렬) 방식의 변형으로 Pivot를 2개를 사용해 3개의 영역으로 분할하여 영역별로 정렬해주는 방식이라고 한다. Quick Sort처럼 평균 시간 복잡도는 ***O(NlogN)***으로 최악의 경우 ***O(N^2)***을 갖는다.

1. 먼저 왼쪽 끝 숫자를 LP로, 오른쪽 끝 숫자를 RP로 설정하고 LP > RP인 경우 서로의 위치를 바꾸어 준다.
![](https://static.blex.me/images/content/2022/10/9/20221090_chLOJdSA9zvG9bpNP3NP.png)  
2. LP와 RP를 기준으로 3개의 영역으로 나눈다. X < LP / LP < X < RP / RP < X로 나누어진다.
![](https://static.blex.me/images/content/2022/10/9/20221090_yZq0g4baIFbYaUUlq9hj.png)  
3. 나누어진 영역 별로 Dual-Pivot Quick Sort를 진행한다.
![](https://static.blex.me/images/content/2022/10/9/20221090_ltRDYesKhdL0LMoHlOnu.png)


### 소스 코드

##### Java
```java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Baek2750 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        Arrays.sort(N);

        for (int i = 0; i < num; i++) {
            System.out.println(N[i]);
        }
    }
}
```

##### Python
```python
num = int(input())
list = []

for i in range(num):
    list.append(int(input()))

list.sort()

for i in range(num):
    print(list[i])
```

### 참고
[[Dual-Pivot Quick Sort] 두 개의 피봇으로 퀵 정렬](https://cs-vegemeal.tistory.com/53)  
[Dual-Pivot Quicksort Explained and Implemented with Examples in Java](https://youtu.be/XYVbjQXkmiI)