# 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')
  ```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://onehunnitconst.gitbook.io/main/algorithms/ps/boj/2751.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.