안정 정렬과 불안정 정렬

들어가는 말

정렬할 때 기준이 되는 값을 키(Key)라고 한다.
안정 정렬(Stable Sort)은 키가 같은 원소들의 상대적인 순서를 정렬한 뒤에도 유지하는 정렬이다.
반대로 불안정 정렬(Unstable Sort)은 키가 같은 원소들의 상대적인 순서가 바뀔 수 있는 정렬이다.

배열 2(A) 1 2(B)를 예로 들어 보자.
괄호 안의 알파벳은 값이 같은 두 원소를 구분하기 위한 정보다.
이 배열을 오름차순으로 안정 정렬하면 1 2(A) 2(B)가 된다.
두 원소의 키는 모두 2이지만, 입력에서 2(A)가 2(B)보다 앞에 있었으므로 정렬한 뒤에도 그 순서가 유지된다.
반면 불안정 정렬은 키가 같은 원소의 상대적인 순서를 보장하지 않으므로 결과가 1 2(B) 2(A)가 될 수도 있다.

단순한 정수 배열에서는 같은 값을 가진 원소를 서로 구분할 수 없기 때문에 안정 정렬과 불안정 정렬의 차이가 드러나지 않는다.
하지만 학생의 성적과 이름처럼 하나의 원소에 여러 정보가 들어 있다면 두 정렬의 차이가 분명해진다.

여러 기준으로 정렬하기

학생들을 성적이 높은 순서로 정렬하되, 동점자는 이름순으로 나열한다고 하자.
두 기준을 적용하는 순서와 정렬 방식에 따라 결과가 어떻게 달라지는지 살펴보자.

이름순 정렬 후 성적순 정렬

정렬 전:
90(이영희) 100(박철수) 90(김민수) 100(김철수)

이름순 정렬 후:
90(김민수) 100(김철수) 100(박철수) 90(이영희)

이후 성적순으로 정렬하면:
├─ 안정 정렬
│  100(김철수) 100(박철수) 90(김민수) 90(이영희)
│
└─ 불안정 정렬의 가능한 결과
   100(박철수) 100(김철수) 90(이영희) 90(김민수)

이 예시에서는 이름순 정렬에 안정 정렬과 불안정 정렬 중 어느 방식을 사용해도 이름순 정렬 결과가 같다.
두 방식의 차이는 키가 같은 원소들의 상대적인 순서를 유지하는지에 있는데, 여기서는 이름이 같은 학생이 없기 때문이다.

성적순 안정 정렬은 이름순 정렬에서 만들어진 두 학생의 순서를 유지하므로 김철수가 박철수보다 앞에 놓인다.
마찬가지로 성적이 90인 김민수와 이영희의 이름순도 유지된다.
반면 성적순 불안정 정렬은 성적이 같은 학생들의 이름순을 보장하지 않는다.

성적순 정렬 후 이름순 정렬

정렬 전:
90(이영희) 100(박철수) 90(김민수) 100(김철수)

성적순 안정 정렬 후:
100(박철수) 100(김철수) 90(이영희) 90(김민수)

이후 이름순으로 정렬하면:
├─ 안정 정렬
│  90(김민수) 100(김철수) 100(박철수) 90(이영희)
│
└─ 불안정 정렬
   90(김민수) 100(김철수) 100(박철수) 90(이영희)

위 예시에서는 성적순으로 안정 정렬한 뒤 이름순으로 안정 정렬하거나 불안정 정렬했다.
두 경우 모두 학생들이 이름순으로 다시 정렬되면서 앞에서 성적순으로 정렬한 결과가 흐트러졌다.

그렇다면 성적순 안정 정렬을 불안정 정렬로 바꾸면 원하는 결과를 얻을 수 있을까?
성적순 불안정 정렬은 성적이 같은 학생들의 순서를 바꿀 수 있다.
하지만 다음 이름순 정렬에서 모든 학생의 순서가 이름을 기준으로 다시 정렬된다.
따라서 성적순 불안정 정렬로 동점자의 순서가 바뀌더라도 최종 결과에는 영향을 주지 않는다.

이처럼 두 가지 기준을 차례로 적용할 때는 덜 중요한 기준인 이름으로 먼저 정렬한 뒤, 더 중요한 기준인 성적으로 안정 정렬해야 한다.

정렬 알고리즘별 안정성

정렬 알고리즘은 구현 방식에 따라 안정 정렬이 될 수도 있고 불안정 정렬이 될 수도 있다.
아래 표와 본문에서는 널리 사용되는 구현 방식을 기준으로 각 알고리즘을 분류한다.

정렬 알고리즘	안정성	이유
버블 정렬	안정	키가 같은 인접 원소는 교환하지 않는다.
선택 정렬	불안정	최솟값과 앞쪽 원소를 교환하는 과정에서 같은 키의 순서가 바뀔 수 있다.
삽입 정렬	안정	키가 같은 원소를 지나서 이동하지 않는다.
힙 정렬	불안정	멀리 떨어진 원소를 교환하는 과정에서 같은 키의 순서가 바뀔 수 있다.
병합 정렬	안정	키가 같으면 왼쪽 부분 배열의 원소를 먼저 가져온다.
퀵 정렬	불안정	분할 과정에서 멀리 떨어진 원소를 교환한다.
기수 정렬	안정	각 자릿수를 안정적으로 정렬해 이전 자릿수의 순서를 유지한다.
버킷 정렬	구현에 따라 다름	버킷 내부에서 사용하는 정렬 알고리즘에 영향을 받는다.
계수 정렬	구현에 따라 다름	누적 합과 보조 배열을 사용하면 안정적으로 구현할 수 있다.

버블 정렬

버블 정렬은 인접한 두 원소의 순서가 정렬 기준에 맞지 않을 때만 두 원소를 교환한다.
키가 같은 두 원소는 교환할 필요가 없으므로 상대적인 순서가 유지된다.

2(A) 2(B) 1을 오름차순으로 정렬하면 다음과 같이 진행된다.

Before sorting: 2(A) 2(B) 1
Pass 1:         2(A) 1    2(B)
Pass 2:         1    2(A) 2(B)

1회차에서는 먼저 2(A)와 2(B)를 비교하지만 두 값이 같으므로 교환하지 않는다.
이어서 2(B)와 1을 비교하여 두 원소를 교환하면 2(B)가 마지막 인덱스에 놓이고 1회차가 끝난다.

2회차에서는 2(A)와 1을 비교하여 두 원소를 교환한다.
2(B)가 놓인 마지막 인덱스는 1회차에서 이미 확정되었으므로 비교 대상에서 제외되고 2회차가 끝난다.

이처럼 값이 같은 원소들의 정렬 전 상대적 순서가 유지되므로 버블 정렬은 일반적으로 안정 정렬이다.

선택 정렬

선택 정렬은 미정렬 구간에서 최솟값을 찾은 뒤 미정렬 구간의 첫 번째 원소와 교환한다.
이때 서로 멀리 떨어진 두 원소를 교환하므로 그 사이에 있는 같은 키의 원소들의 상대적인 순서가 바뀔 수 있다.

Before sorting: 2(A) 2(B) 1
Pass 1:         1    2(B) 2(A)
Pass 2:         1    2(B) 2(A)

1회차에서는 0번 인덱스에 놓일 원소를 확정하기 위해 미정렬 구간을 순회한다.
순회하여 찾은 최솟값 1을 0번 인덱스의 2(A)와 교환하면 2(A)가 2(B)의 뒤로 이동한다.

2회차에서는 1번 인덱스에 놓일 원소를 확정하기 위해 남은 미정렬 구간을 순회한다.
2(A)와 2(B)의 값이 같으므로 1번 인덱스의 2(B)가 최솟값으로 유지되어 교환은 일어나지 않는다.

이처럼 값이 같은 원소들의 상대적인 순서가 바뀔 수 있으므로 일반적인 선택 정렬은 불안정 정렬이다.

삽입 정렬

삽입 정렬의 안정성은 값이 같은 앞쪽 원소를 이동시키는지에 따라 달라진다.
일반적인 삽입 정렬은 현재 원소보다 큰 앞쪽 원소들을 한 칸씩 뒤로 이동시키고 현재 원소를 그 과정에서 생긴 빈자리에 삽입한다.
이때 값이 같은 앞쪽 원소는 이동하지 않으므로 현재 원소는 해당 원소보다 뒤에 삽입되고 상대적인 순서가 유지된다.

Before sorting: 2(A) 2(B) 1
Pass 1:         2(A) 2(B) 1
Pass 2:         1    2(A) 2(B)

1회차에서는 1번 인덱스의 2(B)를 앞쪽의 정렬된 구간에 삽입하기 위해 2(A)와 비교한다.
두 값이 같으므로 2(A)는 뒤로 이동하지 않고 2(B)는 1번 인덱스에 그대로 놓인다.

2회차에서는 2번 인덱스의 1을 앞쪽의 정렬된 구간에 삽입하기 위해 2(B)와 2(A)를 차례로 비교한다.
두 원소 모두 1보다 크므로 한 칸씩 뒤로 이동하고 1은 0번 인덱스에 삽입된다.
이 과정에서 2(A)와 2(B)가 같은 방향으로 이동하므로 두 원소의 상대적인 순서는 유지된다.

힙 정렬

힙 정렬은 배열을 최대 힙으로 구성한 뒤 루트의 최댓값을 미정렬 구간의 마지막 원소와 교환한다.
이때 서로 멀리 떨어진 두 원소를 교환하므로 그 사이에 있는 같은 키의 원소들의 상대적인 순서가 바뀔 수 있다.

Before sorting: 2(A) 2(B) 1
Build max heap: 2(A) 2(B) 1
Pass 1:         2(B) 1    2(A)
Pass 2:         1    2(B) 2(A)

최대 힙을 구성할 때는 루트의 2(A)가 두 자식보다 작지 않으므로 원소를 교환하지 않는다.

1회차에서는 루트의 2(A)와 미정렬 구간의 마지막 원소인 1을 교환하여 2(A)의 위치를 확정한다.
이후 루트로 이동한 1과 왼쪽 자식인 2(B)를 교환하여 남은 미정렬 구간을 다시 최대 힙으로 만든다.

2회차에서는 루트의 2(B)와 미정렬 구간의 마지막 원소인 1을 교환하여 정렬을 마친다.
그 결과 입력에서 2(A)보다 뒤에 있던 2(B)가 2(A)보다 앞에 놓인다.

이처럼 값이 같은 원소들의 상대적인 순서가 바뀔 수 있으므로 일반적인 힙 정렬은 불안정 정렬이다.

병합 정렬

병합 정렬의 안정성은 값이 같은 두 원소 중 어느 쪽 부분 배열의 원소를 결과 배열에 먼저 저장하는지에 따라 달라진다.
일반적인 병합 정렬은 정렬된 두 부분 배열의 앞쪽 원소를 비교하여 더 작은 원소부터 결과 배열에 저장한다.
이때 두 원소의 값이 같을 때 왼쪽 부분 배열의 원소를 먼저 저장하면 상대적인 순서가 유지된다.

Before sorting: 2(A) 2(B) 1
Split:          [2(A)] [2(B)] [1]
Merge 1:        [2(A) 2(B)] [1]
Merge 2:        [1 2(A) 2(B)]

먼저 배열을 원소가 하나씩 남을 때까지 분할한다.

1회차에서는 왼쪽 부분 배열의 2(A)와 오른쪽 부분 배열의 2(B)를 병합한다.
두 값이 같으므로 왼쪽 부분 배열의 2(A)를 먼저 저장한 뒤 2(B)를 저장한다.

2회차에서는 왼쪽 부분 배열의 2(A) 2(B)와 오른쪽 부분 배열의 1을 병합한다.
1을 먼저 저장한 뒤 왼쪽 부분 배열에 남은 2(A)와 2(B)를 차례대로 저장한다.

이처럼 값이 같은 원소들의 상대적인 순서가 유지되므로 일반적인 병합 정렬은 안정 정렬이다.

퀵 정렬

퀵 정렬은 피벗을 기준으로 배열을 두 부분으로 나누고 각 부분을 재귀적으로 정렬한다.
여기서는 왼쪽 포인터가 피벗 이상의 원소에서 멈추고 오른쪽 포인터가 피벗 이하의 원소에서 멈추는 분할 방식을 예로 든다.
두 포인터가 엇갈리지 않았다면 포인터가 가리키는 두 원소를 교환한다.
이때 서로 떨어진 원소를 교환하므로 값이 같은 원소들의 상대적인 순서가 바뀔 수 있다.

Before sorting:     2(A) 1 2(B)
After partition 1: [1] | [2(A) 2(B)]
After partition 2: [1] | [2(B)] | [2(A)]

첫 번째 분할에서는 가운데 원소인 1을 피벗으로 선택한다.
왼쪽 포인터가 가리키는 2(A)와 오른쪽 포인터가 가리키는 1을 교환하면 왼쪽 구간과 오른쪽 구간이 1과 2(A) 2(B)로 나뉜다.

원소가 하나뿐인 왼쪽 구간은 정렬이 완료되었으므로 오른쪽 구간을 살펴보자.
두 번째 분할에서는 오른쪽 구간의 2(A)를 피벗으로 선택한다.
왼쪽 포인터는 2(A)에서 멈추고 오른쪽 포인터는 2(B)에서 멈춘다.
두 포인터가 엇갈리지 않았으므로 두 원소를 교환한다.

제자리 분할(in-place partition)은 별도의 배열을 사용하지 않고 원본 배열 안에서 원소를 교환한다.
이 과정에서 값이 같은 원소들의 상대적인 순서가 바뀔 수 있다.
따라서 이 분할 방식을 사용하는 퀵 정렬은 불안정 정렬이다.

계수 정렬

계수 정렬을 단순하게 구현하면 각 값의 빈도만 센 뒤 원본 배열을 차례로 다시 채운다.
이 방식은 같은 값을 가진 원소의 부가 정보를 구분하지 못하므로 불안정 정렬이다.

반면 빈도 배열의 누적 합을 구한 뒤 원본 배열을 마지막부터 순회해 배치하면 값이 같은 원소의 입력 순서가 유지되어 안정적인 정렬이 된다.

Before sorting: 2(A) 2(B) 1
Place 2(B):     _    _    2(B)
Place 2(A):     _    2(A) 2(B)
Place 1:        1    2(A) 2(B)

버킷 정렬

버킷 정렬의 안정성은 원소를 버킷에 넣는 방식과 각 버킷의 내부 정렬에 따라 달라진다.
값이 같은 원소들을 입력 순서대로 같은 버킷에 넣고 안정 정렬하면 상대적인 순서가 유지된다.
반면 버킷에 넣는 과정에서 순서가 바뀌거나 불안정한 내부 정렬을 사용하면 상대적인 순서가 바뀔 수 있다.

Before sorting:       12(A) 12(B) 11 21
Bucket 1 (10 to 19):  12(A) 12(B) 11
Bucket 2 (20 to 29):  21
Stable result:        11    12(A) 12(B) 21
Unstable result:      11    12(B) 12(A) 21

먼저 12(A), 12(B), 11을 입력 순서대로 10 이상 20 미만인 원소를 담는 버킷에 넣고 21을 다음 버킷에 넣는다.

각 버킷을 안정 정렬하면 값이 같은 12(A)와 12(B)의 순서가 유지된다.
이후 버킷을 순서대로 합치면 11 12(A) 12(B) 21이 된다.

반면 버킷 내부에서 불안정 정렬을 사용하면 12(A)와 12(B)의 순서가 바뀔 수 있다.
이 상태로 버킷을 합치면 11 12(B) 12(A) 21이 될 수 있다.

이처럼 버킷 정렬은 원소를 버킷에 넣는 방식과 버킷 내부에서 사용하는 정렬 알고리즘에 따라 안정성이 달라진다.

기수 정렬

기수 정렬은 일반적으로 각 자릿수를 계수 정렬로 정렬한다.
이때 안정적인 계수 정렬을 사용하면 이전 자릿수의 순서가 유지되므로 기수 정렬도 안정 정렬이다.