문제출처
https://www.acmicpc.net/problem/2751
개요
N개의 수가 주어졌을 때 오름차순으로 정렬하는 알고리즘을 짜는 문제다.
문제접근
시간복잡도
알고리즘이 2초 안에 최대 1,000,000(백만)개의 데이터를 정렬할 수 있어야한다. 시간복잡도가 최대 O(2NlogN)이면 백만개의 데이터를 2초 안에 처리할 수 있다.
알고리즘: 병합정렬
데이터를 2NlogN 안에 정렬을 해야한다. 정렬 중에 힙정렬, 병합정렬이 NlogN의 시간복잡도를 가진다. 버블정렬, 선택정렬은 구현하기 편하나 시간복잡도가 N^2이기 때문에 배제한다.
코드구현
파이썬
from sys import stdin
input = stdin.readline
n = int(input())
my_list = [int(input()) for x in range(n)]
my_list.sort() // TimSort 알고리즘
for number in my_list:
print(number)파이썬은 my_list.sort()를 통해 리스트의 원소들을 쉽게 정렬 할 수 있다. sort()함수는 내부적으로 timsort 알고리즘을 사용한다. timsort 알고리즘은 병합정렬과 삽입정렬을 조합한 알고리즘으로 시간복잡도가 O(NlogN)이다.
sort()함수는 리스트 객체에서 사용하는 메서드다. 리스트의 요소들을 제자리 정렬을 하며 별도의 값을 반환하지 않는다. 즉, 기존 리스트의 객체 자체의 원소 순서들을 바꾼다.
sort()와 오름차순
my_list = [5,4,3,2,1]
my_list.sort()
print(my_list) # [1,2,3,4,5] 출력
sort()함수는 별도의 매개변수가 없는 경우에는 오름차순으로 원소들을 정렬한다.
sort()와 내림차순
내림차순으로 정렬하고 싶다면 다음처럼 함수의 매개변수에 `reverse=True`를 넣는다.
my_list = [1,2,3,4,5]
my_list.sort(reverse=True)
print(my_list) # [5,4,3,2,1] 출력배운점
- 시간복잡도를 고려해서 알고리즘을 구현할 것
- 파이썬의 sort 함수는 timsort 알고리즘 기반으로 안정적인 정렬을 한다.
- 파이썬으로 리스트를 오름차순으로 정렬할 경우 매개변수를 비워두고 내림차순으로 정렬할 경우 reverse=True를 매개변수에 넣는다.