---
title: "정렬 안정성: 같은 키를 가진 원소의 순서도 정보다"
author: "Lee"
published_at: "2026-10-24T18:40:02.307Z"
updated_at: "2026-09-30T09:50:20.450Z"
tags: ["컴퓨터공학","알고리즘"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/%EC%A0%95%EB%A0%AC-%EC%95%88%EC%A0%95%EC%84%B1-%EA%B0%99%EC%9D%80-%ED%82%A4%EB%A5%BC-%EA%B0%80%EC%A7%84-%EC%9B%90%EC%86%8C%EC%9D%98-%EC%88%9C%EC%84%9C%EB%8F%84-%EC%A0%95%EB%B3%B4%EB%8B%A4"
ai_assisted: false
---

# 정렬 안정성: 같은 키를 가진 원소의 순서도 정보다

[원문](https://ariser.io/@writer_a1cd615ab19e/%EC%A0%95%EB%A0%AC-%EC%95%88%EC%A0%95%EC%84%B1-%EA%B0%99%EC%9D%80-%ED%82%A4%EB%A5%BC-%EA%B0%80%EC%A7%84-%EC%9B%90%EC%86%8C%EC%9D%98-%EC%88%9C%EC%84%9C%EB%8F%84-%EC%A0%95%EB%B3%B4%EB%8B%A4)

정렬 안정성은 비교 키가 같은 원소들의 상대 순서를 원래 입력대로 유지하는 성질이다. 키가 같으면 어떤 순서여도 정렬 결과는 맞을 수 있지만, 그 순서에 다른 정보가 담겨 있을 때 안정성이 중요하다.

![같은 키를 가진 A와 C 및 B와 D의 상대적 순서를 유지하는 안정 정렬](/api/v1/media/27452ee0-da7e-475e-83f7-095df3eb4fb2)

*키가 같을 때 입력에서의 상대적 순서를 유지한다.*

### 키와 레코드를 구분하기

학생 목록이 (지민,90),(민수,80),(서연,90) 순서라면 성적 오름차순의 안정 결과는 (민수,80),(지민,90),(서연,90)이다. 90점인 두 학생은 입력 순서를 유지한다. 점수 숫자만 보면 이 차이를 관찰할 수 없으므로 안정성은 보통 이름이나 ID 같은 부가 정보와 함께 확인한다.

다음은 Python의 안정 정렬을 이용해 두 키를 단계적으로 적용하는 예다. 마지막 정렬의 키가 최우선 기준이 된다는 순서가 중요하다.

```python
students = [
    {"name": "Jimin", "score": 90},
    {"name": "Minsu", "score": 80},
    {"name": "Seoyeon", "score": 90},
]
by_name = sorted(students, key=lambda student: student["name"])
by_score_then_name = sorted(by_name, key=lambda student: student["score"])
# Equal scores retain the name order created by the first sort.
```

같은 결과를 (score,name) 복합 키로 한 번에 정렬할 수도 있다. 여러 번 정렬하는 방식에서는 낮은 우선순위 기준부터 처리해야 이후 안정 정렬이 그 기준을 동률 안에 보존한다.

### 구현의 선택이 성질을 바꾼다

병합 정렬은 동률에서 왼쪽 원소를 먼저 선택하면 안정성을 얻는다. 삽입 정렬은 현재 키보다 엄격히 큰 원소만 뒤로 밀면 같은 키를 건너뛰지 않는다. 계수 정렬도 출력 위치와 입력 읽기 방향을 맞춰 안정적으로 만들 수 있다.

전형적인 퀵 정렬이나 힙 정렬은 먼 원소를 교환해 같은 키 순서를 바꿀 수 있어 비안정이다. 하지만 알고리즘 이름만으로 모든 변형의 성질을 단정하면 안 된다. 안정 변형은 존재하며 보조 공간이나 비용이 달라질 수 있다.

안정성과 제자리성은 별개다. 추가 메모리를 얼마나 쓰는지와 동률 순서를 보존하는지는 다른 축이다. 안정 정렬이라고 자동으로 느리거나 O(n) 보조 공간이 필수라는 결론도 일반적으로 성립하지 않는다.

비안정 정렬을 써야 한다면 (키,원래 인덱스)를 비교해 동률 순서를 명시할 수 있다. 이때 비교 키가 달라진 결과이며 원래 정렬 알고리즘 자체의 안정성이 바뀐 것은 아니다. 인덱스 저장 비용도 생긴다.

동률 순서가 중요하지 않다면 안정성은 필수 조건이 아닐 수 있다. 반대로 사용자에게 보이는 목록, 여러 기준의 단계 정렬, 시간순 레코드에서는 의미 있는 요구다. 먼저 무엇을 같은 키로 보고 어떤 순서를 보존할지 정해야 적절한 정렬을 고를 수 있다.

비교 키에 시각을 포함하면 동일 점수 안에서 시간순을 명시할 수 있다. 안정성과 원하는 동률 정책이 같은지 먼저 확인해야 한다.

### 참고 자료

- [MIT OpenCourseWare · Introduction to Algorithms](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/)
- [Princeton · Algorithms, 4th edition · Elementary Sorts](https://algs4.cs.princeton.edu/21elementary/)