수 정렬하기 - 2750

2750번: 수 정렬하기

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 간단한 문제

맞았습니다! 풀이

N = int(input())
num = [int(input()) for _ in range(N)]

num.sort()
for n in num:
  print(n)

파이썬 내장 함수인 sort()가 어떤 방법으로 정렬을 하는건지 궁금해서 찾아봤는데

1. 파이썬 내장 파일에 위치하기 때문에 C 언어로 구현되어 있음

2. Tim Peter라는 사람이 만든 정렬이라 Tim Sort 알고리즘이라고 부름

   -> 일반적인 정렬 방식과는 조금 다르게 구현된 듯 하다

3. 원리는 merge sort를 기반으로 하지만, 최적화 기법을 더 추가한 방식
4. 시간 복잡도는 최악의 경우 $O(nlogn)$를 가진다.

실제 TimSort 알고리즘을 구현해둔 github 코드 : cpython/listobject.c

맨 위로 이동하기