[정렬] 6 - 1 파이썬의 정렬 라이브러리

sorted()

• 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌다.
• 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다.
• sorted() 함수는 리스트,딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력한다.
• 집합 자료형이나 딕셔너리 자료형을 입력받아도 반환되는 결과는 리스트 자료형이다.

array = [7, 6, 9, 0, 3, 1, 6, 2, 4, 8]

result = sorted(array)
print(result)

 

 

sort()

리스트 변수가 하나 있을 때 내부 원소를 바로 정렬할 수 있다.

array = [7, 6, 9, 0, 3, 1, 6, 2, 4, 8]

array.sort()
print(array)

sorted()와 sort()를 이용할 때에는 key 매개변수를 입력으로 받을 수 있다.

key 값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다.

array = [('바나나', 2), ('사과', 5), ('당근', 3)]


def setting(data):
    return data[1]


result = sorted(array, key=setting)
print(result)


# [('바나나', 2), ('당근', 3),('사과', 5) ]

 

정렬 라이브러리의 시간 복잡도

• 최악의 경우에도 O(NlogN)

 

코딩 테스트에서 정렬 알고리즘이 사용되는 경우

1. 정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀수 있다. 
2. 정렬 알고리즘의 원리에 대해서 물어보는 문제 : 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.
3. 더 빠른 정렬이 필요한 문제 : 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.