[정렬] 정렬 (3) 파이썬의 정렬 라이브러리

 파이썬의 정렬 라이브러리

• 정렬 알고리즘 문제를 풀 때, 정렬 알고리즘을 직접 작성하는 것보다 미리 만들어진 라이브러리를 이용하는 것이 효과적인 경우가 많음

sorted() 함수

• 파이썬의 기본 정렬 라이브러리에서 제공
• 병합 정렬 기반
  • 퀵 정렬보다 느리지만, 최악의 경우에도 O(NlogN) 시간 복잡도 보장
  • 리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력
  • 이때, 반환되는 결과는 무조건 리스트 자료형
• 소스코드

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

result = sorted(array)
print(result)
# 실행 결과 : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

sort() 함수

• 리스트 객체의 내장 함수
• 리스트 변수가 하나 있을 때 내부 원소를 바로 정렬
• 별도의 정렬된 리스트가 반환되지 않음

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

array.sort()
print(array)
# 실행 결과 : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

key 매개변수

• sorted()나 sort() 이용 시 사용 가능
• key 값으로는 하나의 함수가 들어가야 하며, 이게 정렬 기준이 됨
• 소스코드

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

def setting(data):
  return data[1]

result = sorted(array, key = setting)
print(result)
# 실행 결과 : [('바나나', 2), ('당근', 3), ('사과', 5)]

• 함수 대신 람다 함수를 사용할 수도 있음

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

def setting(data):
  return data[1]

result = sorted(array, key = lambda x: x[1])
print(result)
# 실행 결과 : [('바나나', 2), ('당근', 3), ('사과', 5)]

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

• 항상 최악의 경우에도 시간 복잡도 O(NlogN) 보장
• 퀵 정렬을 직접 구현할 때보다 효과적

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

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