Python 안정 정렬은 키가 같은 항목의 순서를 어떻게 다룰까

Python의 sorted()와 list.sort()는 안정 정렬입니다. 정렬 키가 같은 요소는 입력에서 앞선 순서를 유지하므로, 이전 정렬 결과를 다음 정렬에서 동점 처리의 보조 기준으로 활용할 수 있습니다.

정렬 방향을 바꾸어도 동점의 기존 순서는 유지됩니다. 다단계 정렬은 낮은 우선순위 키부터 정렬한 뒤 높은 우선순위 키를 정렬하거나 복합 키를 사용합니다.

안정 정렬은 동점의 기존 순서를 보존합니다

정렬 결과에서 같은 키를 가진 레코드가 여러 개라면 그 내부 순서가 중요할 수 있습니다. Python 3.12 정렬 안내서와 내장 자료형 문서는 list.sort()가 안정적이라고 명시합니다. 안정 정렬이란 정렬 기준에서 동등한 항목끼리 원래 입력에서의 상대 순서를 유지한다는 뜻입니다. sorted()도 같은 정렬 동작을 제공하며, 차이는 원본을 바꾸지 않고 새 목록을 만드는지(sorted) 원본 목록을 제자리에서 바꾸는지(list.sort)에 있습니다.

점수가 같은 학생의 입력 순서를 추적합니다

다음 자료에서 세 학생의 점수를 내림차순으로 정렬하되, 같은 점수인 학생은 접수 순서를 유지한다고 하겠습니다. key를 점수로 정해 정렬하면 점수가 90인 민서와 도윤은 원래 입력에서 등장한 차례를 유지합니다. 점수 85인 서연은 그 뒤에 옵니다. 이름을 알파벳이나 가나다 순으로 자동 정렬하는 것은 아닙니다. 동점의 기준은 별도로 바꾸지 않는 한 입력의 기존 상대 순서입니다.

students = [("민서", 90), ("도윤", 90), ("서연", 85)]
ranked = sorted(students, key=lambda row: row[1], reverse=True)
print(ranked)

정렬 키는 각 레코드에서 비교할 값을 추출하는 함수입니다. 문서에 따르면 key 함수는 각 입력 요소에 한 번씩 적용됩니다. 따라서 문자열을 정규화하거나 레코드의 필드를 뽑아 정렬할 수 있습니다. 동점이 생겼을 때 안정성이 유용한 이유는 정렬 결과의 앞선 기준을 보존할 수 있기 때문입니다. 다만 입력 순서가 이미 의미 있는 순서여야 합니다. 입력이 데이터베이스 조회 등으로 매번 달라질 수 있다면 먼저 신뢰할 수 있는 기준으로 순서를 정해야 안정 정렬의 효과도 일관됩니다.

여러 기준은 낮은 우선순위부터 적용합니다

예를 들어 부서를 가나다순으로 묶고, 같은 부서 안에서는 점수를 높은 순으로 배열하려면 안정 정렬을 두 번 적용할 수 있습니다. 우선 낮은 우선순위인 점수 내림차순을 만들고, 그 결과에 부서 오름차순 정렬을 적용합니다. 두 번째 정렬에서 부서가 같은 항목들의 기존 상대 순서, 즉 점수 순서가 보존됩니다. 공식 HOWTO는 복합 정렬에서 이 성질을 이용하는 방법을 설명합니다.

records = [("기획", "도윤", 88), ("개발", "민서", 92), ("기획", "서연", 95)]
by_score = sorted(records, key=lambda row: row[2], reverse=True)
by_department_then_score = sorted(by_score, key=lambda row: row[0])
print(by_department_then_score)

1. 정렬 우선순위 중 가장 낮은 기준을 먼저 적용합니다.
2. 각 정렬에서 key와 reverse 방향을 정확히 지정합니다.
3. 다음으로 더 높은 우선순위 기준을 안정 정렬합니다.
4. 최종 목록에서 같은 상위 키끼리 앞선 정렬의 상대 순서가 보존됐는지 확인합니다.
5. 한 번의 복합 키로 표현할 수 있으면 튜플 키로도 간결하게 작성합니다.

복합 키를 사용하면 (부서, -점수)처럼 오름차순·내림차순 기준을 한 표현식으로 합칠 수 있습니다. 다만 문자열처럼 부호 반전이 자연스럽지 않은 키가 끼어 있으면 여러 번의 안정 정렬이 읽기 쉽습니다. list.sort()를 쓸 때는 원본 목록이 바뀌고 반환값은 정렬된 목록이 아니라 None이라는 점도 기억해야 합니다. 결과를 변수에 담으려면 records.sort(...) 자체를 대입하지 말고, 제자리 변경이 필요하지 않으면 sorted(records, ...)를 선택하세요.

안정성은 동점 순서를 임의로 새로 정하지 않습니다

흔한 오해는 안정 정렬이 동점인 항목을 언제나 이름순으로 유지하거나, 동점 기준을 자동으로 만들어 준다고 보는 것입니다. 안정성은 정렬 키가 같을 때 입력 순서를 보존할 뿐입니다. 입력 순서가 뒤섞여 있다면 그 뒤섞인 순서가 그대로 남습니다. 또 내림차순 정렬에서 동점의 상대 순서가 뒤집힌다고 생각하기 쉽지만 Python의 안정성은 reverse=True에서도 유지됩니다. 원하는 동점 규칙이 ‘먼저 등록된 항목 우선’이라면 입력 순서가 등록 순서를 반영하도록 하고, 그 전제가 깨지면 등록 시각 같은 보조 키를 명시해야 합니다.

입력: [(민서, 90), (도윤, 90), (서연, 85)]
점수 내림차순: 민서 90, 도윤 90, 서연 85
보장: 점수 90의 기존 상대 순서 유지
비보장: 이름순, 입력의 신뢰성, 별도 동점 규칙 자동 생성

정렬 테스트를 만들 때는 키가 서로 다른 사례만 넣지 말고 동점 항목도 포함하세요. 그래야 안정성에 기대는 코드와 키 함수가 실제로 의도한 필드를 선택하는지 검증할 수 있습니다. 정렬 알고리즘의 내부 구현이나 비교 횟수를 암기하는 것보다, 입력 순서·키·방향·동점 처리를 분리해 결과를 손으로 추적하는 편이 실기형 문제에 도움이 됩니다.