[Algorithm] 안정 정렬과 불안정 정렬의 차이점

[Algorithm] 안정 정렬과 불안정 정렬의 차이점

 

 

 

2023.01.19 - [Algorithm] - [Swift] 프로그래머스 문자열 내 마음대로 정렬하기(lv. 1)

[Swift] 프로그래머스 문자열 내 마음대로 정렬하기(lv. 1)

드디어 이것에 대한 답을 어느정도 이해하고 포스팅할 시간이 왔다.

 

이전에 품었던 의문이었다.

 

이 부분은 안정 정렬과 불안정 정렬의 정의를 먼저 알아보고 가야한다.

 

 

1. 안정 정렬과 불안정 정렬의 정의

 

1) 안정 정렬

 

안정 정렬은 중복된 값을 입력 순서와 동일하게 정렬한다.

중복된 값을 입력 순서와 동일하게 정렬한다는 말은, 다른 말로 '기존의 다른 요소로 정렬이 된 입력값을 정렬할 때, 기존의 정렬 형태를 유지한 상태에서 정렬을 한다는 의미'이다.

'딕셔너리'를 정렬하거나, '이차원 배열'을 정렬하다 보면 느낄 수 있는 것이다.

 

쉽게 그냥 '이차원 배열'을 정렬하는 것을 가정해보자.

var array = [[서울, 19세], [서울, 20세], [광주, 5세], [서울, 23세], [울산, 19세], [광주, 20세], [울산, 31세]]

이런 배열이 있다고 해보자. 현재 배열은 각 지역 별로 '나이'를 기준으로는 오름차순 배열이 되어 있다.

서울 19, 20, 23세 / 광주 5, 20세 / 울산 19, 20세

 

전체 배열을 그러면 '지역'을 기준으로 오름차순 배열을 해본다면?

 

안정 정렬은 '기존 정렬 형태를 유지하면서 정렬'을 한다.

var array = [[광주, 5세], [광주, 20세], [서울, 19세], [서울, 20세], [서울, 23세], [울산, 19세], [울산, 31세]]

 

이렇게 뒤의 나이의 순서 정렬은 바뀌지 않고 정렬이 될 것이다.

 

 

2) 불안정 정렬

 

불안정 정렬(Unstable Sort)은 중복된 값을 입력 순서와 상관없이 무작위로 뒤섞인 상태에서 정렬이 이루어진다. 기존에 정렬이 되어 있는 상태를 무시하고 전체 정렬된 순서가 바뀔 수도, 바뀌지 않을 수도 있는 정렬인 것이다.

위의 예시로 똑같이 설명해보면 아래와 같다.

 

var array = [[서울, 19세], [서울, 20세], [광주, 5세], [서울, 23세], [울산, 19세], [광주, 20세], [울산, 31세]]

현재 배열은 각 지역 별로 '나이'를 기준으로는 오름차순 배열이 되어 있다. 전체 배열을 그러면 '지역'을 기준으로 오름차순 배열을 해본다면?

 

불안정 정렬은 '기존 정렬 형태를 무시하고 정렬'을 한다.

var array = [[광주, 5세], [광주, 20세], [서울, 19세], [서울, 20세], [서울, 23세], [울산, 19세], [울산, 31세]]

어어...? 안정 정렬과 똑같이 된 거 아닌가?

 

그렇지 않다. 그 정렬을 한 번 더 하면 다르게 바뀔 수도 있다.

 

var array = [[광주, 5세], [광주, 20세], [서울, 23세], [서울, 19세], [서울, 20세], [울산, 19세], [울산, 31세]]

서울의 정렬을 보면 나이순이 뒤 바뀐 것을 알 수 있다. 이렇게 기존의 정렬된 상태를 보장하지 않는 정렬이 불안정 정렬인 것이다.

 

 

3) 정리

 

어떤 정렬 기준이 들어갔을 때, 기존 배열의 '정렬' 상태를 유지하는 지, 유지를 보장하지 않는 지가 차이점 인 것이다.

 

 

 

2. 안정, 불안정 정렬 알고리즘의 예시

 

1) 안정 정렬 알고리즘

 

안정 정렬 알고리즘으로는 삽입 정렬(Insertion Sort), 버블 정렬(Bubble Sort), 병합 정렬(Merge Sort)이 있다.

 

삽입 정렬은 앞에서부터 적절한 위치에 '끼워' 넣는다. [2(1), 2(2), 1, 5]라는 배열이 있다고 하자.

그러면 2(1)을 기준으로 끼워넣기를 할 것이다.

2(2)는 작지 않기 때문에 그대로, 1은 2(1)보다 작기 때문에 앞으로, 5는 2(1)보다 크기 때문에 그대로가 된다.

[1, 2(1), 2(2), 5]가 될 것이다.

 

최종적으로 [1, 2(1), 2(2), 5]로 정렬이 된다.

 

만약, [5, 2(1), 2(2), 1]을 정렬한다면...? 5보다 2(1)은 작기 때문에 앞에 위치한다.

그 다음 2(2)는 2와 5사이에 삽입하여 정렬한다. 1은 5보다 작고, 2보다도 작기 때문에 2(1) 앞에 온다.

최종적으로 [1, 2(1), 2(2), 5]로 정렬된다.

 

원소가 어디에 있든 [1, 2(1), 2(2), 5]로 정렬될 수 밖에 없다. 그래서 안정 정렬 알고리즘이라고 할 수 있는 것이다.

 

 

병합 정렬도 안정적이다.

 

[1, 3, 2(1), 2(2)] 라는 배열이 있다고 하자.

첫 번째 병합에서는 1, 3 / 2(1), 2(2) 로 병합이 될 것이다.

두 번째 병합에서는 1, 2(1), 2(2), 3으로 병합이 된다.

 

그럼 원소의 위치를 바꿔서 [2(1), 3, 1, 2(2)]라는 배열이 있다고 하자.

첫 번째 병합에서는 2(1), 3 / 1, 2(2) 로 병합이 될 것이다.

두 번째 병합에서는 1, 2(1), 2(2), 3으로 병합이 될 것이다.

 

원소 2에 붙은 (1), (2)가 계속 순서가 유지됨을 알 수 있다.

 

삽입 정렬, 병합 정렬은 기존에 있는 순서를 가지고 정렬을 하는 알고리즘이리고 할 수 있다. 기존 순서를 뒤집지 않기 때문에 안정된 정렬을 할 수 있는 것이다.

 

 

2) 불안정 정렬 알고리즘

 

불안정 정렬 알고리즘으로는 선택 정렬(Selection Sort), 퀵 정렬(Quick Sort), 힙 정렬(Heap Sort)이 있다.

 

선택정렬은 가장 작은 수를 n번 인덱스와 바꾸면서 오름차순 정렬을 한다.

 

[2(1), 2(2), 1, 5] 라는 배열이 있다고 하자(괄호는 동일한 수이지만, 1번, 2번이라고 가정을 한 것이라고 생각하자).

그러면, 스와프가 일어나면서 첫 번째 반복 때는 [1, 2(2), 2(1), 5]로 바뀔 것이다.

두 번째는 앞에서 부터 원소를 읽어가며 최소값을 판별할 것인데, 2(2)가 먼저 읽히므로, 2(2)가 최소값이 된다.

최종적으로 [1, 2(2), 2(1), 5]로 정렬이 끝날 것이다.

 

그런데, [5, 2(1), 2(2), 1]을 정렬한다면...?

위의 반복과 교체를 거치면 [1, 2(1), 2(2), 5]가 도출될 것이다.

어쨌든, 내부 원소의 배열에 따라 정렬의 결과가 달라지는 것을 볼 수 있다.

 

그렇기에 불안정 정렬 알고리즘이라고 하는 것이다.

 

퀵 정렬도 불안정하다.

 

[5, 2(1), 1, 2(2)]라는 배열이 있다고 하자.

피벗을 1로 한다면, 첫 번째 분할 때는 [1, 2(2), 2(1), 5]가 될 것이다. 

그러면 [5, 2(2), 1, 2(1)]일 때는?

[1, 2(1), 2(2), 5]가 될 것이다.

 

사실, 퀵 정렬은 피벗을 무엇으로 하냐에 따라서도 달라질 수 있다.

피벗에 따라 각 원소를 바꾸는 위치도 다르고 하기 때문에 기존에 정렬된 값은 제대로 무시를 하고 정렬이 된다고 보아야 한다.

 

선택 정렬, 퀵 정렬과 같은 것은 정렬을 하는 기준이 각각 달라질 수 있기 때문에 매번 정렬을 할 때 마다 기존에 정렬된 부분들이 바뀔 수 있다. 그렇기에 불안정한 정렬이라고 할 수 있는 것이다.

 

 

3. 정리

 

어떤 정렬의 기준 또는 방식에 따라 기존의 정렬을 유지하는 지, 유지하지 않는 지가 달라진다고 할 수 있을 것이다.

고정된 기준을 가지고 비교를 하고 정렬을 한다면 안정적일 것이고, 변하는 기준에 따라 비교를 하고 정렬을 한다면 불안정적일 것이다.

 

불안정 하다고 해서 성능이 좋지 않은 것은 아니다. 기존의 정렬된 값이 필요없다면, 퀵 정렬은 난수에 가까운 수들을 정렬하는데 아주 효과적인 것이라고 할 수 있다. 그럴 때 퀵 정렬을 활용하거나 할 수 있는 것이다.

 

필요한 상황과 때, 그리고 환경에 맞추어서 안정, 불안정 정렬을 잘 구분해서 써야겠다는 생각을 할 수 있었다.

 

다음에는 좀 더 심화된 정렬 알고리즘 들을 알아볼 것이다.