🐍sort()와 sorted() 차이점 + 다른 정렬 방식 비교

관련글 :

정렬 알고리즘	https://waydd.tistory.com/10
bisect	https://waydd.tistory.com/117
functools	https://waydd.tistory.com/58

 

 

1. 핵심 정리

• Timsort ( 삽입 정렬 + 합병 정렬 ) 알고리즘 사용 + 안정 정렬(Stable Sort)
  ①  Run(런) 탐색 : 리스트에서 연속된 오름차순·내림차순 구간을 찾음
  ②  삽입 정렬 : 작은 구간(run)들은 삽입 정렬로 빠르게 정렬
  ③  합병 정렬(Merge Sort) 방식 병합 : 정렬된 run들을 병합하면서 전체 정렬 완성
  → 작은 구간은 삽입 정렬 + 큰 구간은 병합 정렬로 병합
  → 최악, 평균 : O(N log N)
  → 거의 정렬되어 있는 데이터일수록 삽입 정렬이 유리  (O(N) 에 가까운 성능)
  → 공간복잡도 : O(N) (병합 과정에서 일부 추가 메모리 사용)
• 둘다 기본 정렬은 오름차순 정렬
• .sort() : 리스트만 사용 가능, 객체 자체를 직접 정렬( 제자리 정렬 ), 리턴값은 None
• sorted(iterable) : 내장 함수, iterable 객체라면 사용 가능, 정렬된 새로운 복사본 반환(리턴), 원본은 변경 없음

※ 안정 정렬이란? 동일한 키 값을 가진 원소들의 상대적 순서 유지 (정렬 전후 같은 값끼리 기존 순서 변하지 X)

※ sorted() 함수는 반복 가능한 객체 라면 정렬 가능
- set도 순서 없는 집합이지만 반복 가능하기 때문에 가능
  → 내부적으로 집합을 리스트로 변환 후 정렬
  → list(sorted_result) 반환

 

 

- 다른 언어와  비교

• C++ STL의 std::sort : 제자리 정렬, unstable
• Java의 Arrays.sort : primitive는 제자리, 객체는 Timsort 기반 안정 정렬
• Python list.sort() : 제자리 + 안정 정렬

 

 

2. sort() vs sorted() 비교표

	.sort([key=None, reverse=False])	sorted(iterable[, key=None, reverse=False])
정렬 방식	Timsort (안정 정렬)	Timsort (안정 정렬)
반환값	None	새로운 정렬된 리스트
원본 리스트 유지 여부	변경됨	원본 리스트 유지 (복사본만 변경됨)
공간 복잡도	O(1) (제자리 정렬 → 메모리 효율)	O(N) (새 리스트 생성 → 추가 메모리 사용)
사용 시기	리스트 자체를 정렬하고자 할 때 사용	원본을 보존하고 새 리스트가 필요할 때 사용

※ 매개변수 의미
- key : 정렬 기준 함수
  ex) len, abs, str.lower 등 혹은 lambda x: x[1](튜플 특정 요소 기준 정렬) 사용자 정의 함수 
- reverse : 역순 여부

※ key 함수의 반환값 은 정렬 가능한 객체라면 사용 가능  (ex. 튜플로 사전식 비교, 다중 기준 정렬도 가능)

※ Python에서 기본 정렬은 오름차순 (작은값 → 큰 값)

 

 

3. key 함수 사용

 

- key 매개변수 역할 

• 디폴트는 원소 자체의 크기 비교 사용
  → 숫자는 오름차순, 문자열은 사전순 정렬
• key 매개변수는 원소마다 변환된 값 기준으로 정렬 가능 (비교 기준이 될 변환값 지정)
  ※ 원소 → 변환값 → 변환값 끼리 비교 → 원래 원소 순서 결정
• key에 함수(혹은 lambda) 를 전달 시, 리스트 각 원소를 그 함수에 넣어 반환된 결과 가 정렬 기준
  (예시) key = len 사용 : 문자열 길이 기준 비교 정렬
  ※ key 함수는 원소마다 한번만 호출됨 (그 결과를 캐싱하여 정렬, 다시 호출 X)  → 효율적
• reverse 는 단순 순서 뒤집는 역할, key는 비교 기준 자체를 바꿈
  → 둘다 독립적, 함께 사용 가능
• key 계산 무겁다면 성능 저하 발생 가능 → key 함수 구현시, O(1) 가깝게 구현 필요

- 기본 정렬 (key 사용)

# 자주 사용하는 key 예시
# key=len → 문자열 길이 기준 정렬
# key=str.lower → 대소문자 무시하고 문자열 정렬
# key=lambda x: x[1] → 2차원 배열, 튜플에서 특정 열/원소 기준 정렬
# key=abs → 절댓값을 기준으로 정렬

meetings.sort(key=lambda x: (x[1], x[0]))

 

- 사용자 정의 비교 함수 (cmp_to_key)

from functools import cmp_to_key

def compare(a, b):
    # a = (start1, end1), b = (start2, end2)
    if a[1] == b[1]:
        return a[0] - b[0]   # 시작시간 오름차순
    return a[1] - b[1]       # 끝나는 시간 오름차순

meetings.sort(key=cmp_to_key(compare))

 

 

4. Python 주요 정렬 방식 비교

	내부 알고리즘	시간 복잡도	공간 복잡도	안정성	설명
sorted() / list.sort()	Timsort (삽입+병합 혼합)	O(N log N) / O(N log N)	O(N)	안정 정렬	- 기본 정렬 함수 - key·reverse 지원 - 거의 정렬 상태면 O(N) 근접
heapq (우선순위 큐)	최소 힙 기반	삽입/삭제 O(log N)	O(N)	불안정	- 항상 최솟값 접근 빠름 - 전체 정렬은 O(N log N)
bisect (이진 탐색 모듈)	이진 탐색	탐색 O(log N)	O(1)		- 정렬된 배열 유지용 - 삽입 시 O(N) (리스트 이동 비용)
collections.deque + 정렬	정렬 아님		O(1) 회전		- 단순 큐/덱, 정렬 직접 지원 X
numpy.sort	퀵소트 / 병합 / 힙 등 선택	O(N log N)	O(N)	선택적	- 수치 배열 고속 정렬 - 다차원 정렬 가능
pandas.sort_values	Timsort 기반	O(N log N)	O(N)	안정 정렬	- DataFrame 컬럼 기준 정렬 - NaN 처리 가능