[백준/11004] K번째 수 | Python 정렬 함수의 알고리즘

K번째 수

Baekjoon Online Judge

---

 

알고리즘

N(1<=N<=5,000,000)
Ai(-10**9 <= Ai <= 10**9)

범위가 위와 같이 주어졌기 때문에, List를 정렬하는 sorted()나 sort()로 하면 당연히 시간 초과 코드일 줄 알았는데 의외로 정답이었다.

그래서 이번 기회를 통해 python의 리스트 정렬 연산의 원리와 복잡도에 대해 알아보려한다.

---

 

sort() 

This method sorts the list in place, using only comparisons between items. This method modifies the sequence in place for economy of space when sorting a large sequence. To remind users that it operates by side effect, it does not return the sorted sequence (use sorted() to explicitly request a new sorted list instance). The sort() method is guaranteed to be stable. A sort is stable if it guarantees not to change the relative order of elements that compare equal — this is helpful for sorting in multiple passes (for example, sort by department, then by salary grade).

docs.python.org

 

 sorted()

a new sorted list from the items in iterable. The sort algorithm uses only comparisons between items.
The built-in sorted()function is guaranteed to be stable. A sort is stable if it guarantees not to change the relative order of elements that compare equal — this is helpful for sorting in multiple passes (for example, sort by department, then by salary grade).

docs.python.org

 

sorted, sort 정렬 알고리즘은 Tim Sort

Python의 sort와 sorted의 정렬 방식은 삽입정렬과 병합정렬을 결합한 정렬 방식인 Tim sort 알고리즘 을 사용한다. 정렬 방식에 있어서는 복잡도 차이가 없지만(O(n log n)) sort와 sorted 간 시간 차이가 나는 이유는 원본 리스트를 변경하느냐 변경 하지 않고 새로운 리스트를 반환하느냐에 있다.

 

그렇다면 sort와 sorted의 차이점은?

	sort	sorted
종류	리스트 메소드	파이썬 내장 함수
대상 객체	List만 가능하다.	모든 iterable 객체에 적용 가능하다.
return	None. 원래 있던 리스트의 값으로 정렬을 실행한다.	새로운 리스트 객체를 반환한다.

sort는 원래 있던 리스트를 활용하므로 메모리에 새로운 공간을 확보할 필요가 없다. 이로 인해 메모리 사용량이 적고, 더 빠른 정렬 속도를 보장할 수 있다.

---

전체 코드

import sys; input = sys.stdin.readline

n,k = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
print(arr[k-1])

 

알게된 점

• sort는 리스트 메소드로, 해당 리스트를 변경하는 것이기에 메모리 공간을 그대로 사용한다.
• O(n log n)의 정렬 방식으로는 퀵, 힙, 머지 소트 등이 있다.