> For the complete documentation index, see [llms.txt](https://onehunnitconst.gitbook.io/main/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://onehunnitconst.gitbook.io/main/algorithms/ps/boj/2751.md).

# 2751: 수 정렬하기 2

### **문제의 의도**

수를 정렬하는 정렬 알고리즘을 구현하는 문제이다. 단, n이 최대 1,000,000의 큰 값을 가질 수 있으므로 시간 복잡도가 $O(n\log{n})$ 정도의 빠른 정렬 알고리즘이어야 한다.

### 아이디어

* [이 자료](https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt)에 따르면 파이썬의 `list.sort()` 혹은 `sorted(list)` 는 최악 시간복잡도가 $O(n\log{n})$ 이다. 내부적으로 [Timsort](https://en.wikipedia.org/wiki/Timsort)라고 하는 알고리즘을 사용한다.
* 또한 이 문제의 난이도가 실버 5로 낮은 편이므로, 정렬의 개념을 이해하고 정렬 알고리즘을 사용할 수 있는 수준이면 풀 수 있다고 이해하였다. 물론 **직접 구현**을 하는 것이 조금 더 문제를 정확하게 푸는 방법이나 정렬 알고리즘은 생각보다 그 방법이 방대하며 복잡하다.
* 따라서 이 문제는 파이썬의 내부 정렬 알고리즘을 사용하는 것으로 해결할 수 있다.
* 정렬과 같이 비용을 많이 사용하는 알고리즘의 경우 input()과 print() 때문에 문제가 생길 수 있다. 이를 내장 sys 라이브러리를 사용하여 해결할 수 있다.

### 풀이

* 먼저 몇 개의 숫자를 받을 것인지 입력을 받고, 입력받은 값을 n에 저장한다.
* n번만큼 입력을 받고, 입력받은 수를 list에 추가한다.
* `sorted()` 함수를 이용하여 정렬된 리스트의 요소를 for…in 문으로 하나씩 조회하여 출력한다.
* 성공 (메모리 84924 KB, 시간 1164 ms)

```python
import sys

input = sys.stdin.readline
print = sys.stdout.write

n = int(input().rstrip())
list = []

for index in range(n):
  list.append(int(input().rstrip()))

for num in sorted(list):
  print(str(num) + '\n')
```

### 직접 구현의 경우

* 직접 구현의 경우 알고리즘의 세부적인 이해까지는 시간이 부족하여 수도코드를 기반으로 하여 구현하였다.

![Untitled](https://s3-us-west-2.amazonaws.com/secure.notion-static.com/a45b658a-0eb9-40d0-a9b6-69eaf70f73f8/Untitled.png)

* 퀵 소트: 최악 시간복잡도 $O(n^{2})$, 메모리 초과

  ```python
  import sys

  input = sys.stdin.readline
  print = sys.stdout.write

  def sort(list: list):
    sorted_list = list.copy()
    length = len(sorted_list)

    if length > 1:
      pivot = sorted_list[length-1]
      less = []
      more = []
      equal = []
      for element in sorted_list:
        if element < pivot :
          less.append(element)
        elif element > pivot :
          more.append(element)
        else:
          equal.append(element)
      return sort(less) + equal + sort(more)

    return sorted_list

  n = int(input().rstrip())
  list = []

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

  for num in sort(list):
    print(str(num) + '\n')
  ```
* 힙 소트: 최악 시간복잡도 $O(n\log{n})$

, 성공 (메모리 79064 KB, 시간 6892 ms)

````
```python
def heapify(unsorted_list: list, index: int, heap_size: int): 
  largest = index
  left_index = 2 * index + 1
  right_index = 2 * index + 2
  if left_index < heap_size and unsorted_list[left_index] > unsorted_list[largest]:
    largest = left_index
  if right_index < heap_size and unsorted_list[right_index] > unsorted_list[largest]:
    largest = right_index
  if largest != index:
    unsorted_list[largest], unsorted_list[index] = unsorted_list[index], unsorted_list[largest]
    heapify(unsorted_list, largest, heap_size)

def sort(list: list):
  sorted_list = list.copy()
  length = len(sorted_list)
  for index in range(length // 2 - 1, -1, -1):
    heapify(sorted_list, index, n)

  for index in range(length-1, 0, -1):
    sorted_list[0], sorted_list[index] = sorted_list[index], sorted_list[0]
    heapify(sorted_list, 0, index)

  return sorted_list

n = int(input())
list = []

for index in range(n):
  list.append(int(input()))

print(sort(list))
```
````

* 버블 정렬: 최악 시간복잡도 $O(n^{2})$, 시간 초과

  ```python
  import sys

  input = sys.stdin.readline
  print = sys.stdout.write

  def sort(list: list):
    sorted_list = list.copy()

    for i in range(0, len(sorted_list) - 1):
      minIdx = i
      for j in range (i + 1, len(sorted_list)):
        if (sorted_list[minIdx] > sorted_list[j]):
          minIdx = j
      sorted_list[i], sorted_list[minIdx] = sorted_list[minIdx], sorted_list[i]
    
    return sorted_list

  n = int(input().rstrip())
  list = []

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

  for num in sort(list):
    print(str(num) + '\n')
  ```