안정 정렬(Stable Sort)이란?
안정 정렬(Stable Sort)은 동일한 값을 가진 데이터들의 순서가 원래의 순서와 같이 유지되는 정렬 방법입니다. 이는 데이터가 정렬된 상태에서 어떤 작업을 수행하더라도 데이터의 순서가 바뀌지 않는 것을 의미합니다. 안정 정렬의 예시로는 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort), 병합 정렬(Merge Sort) 등이 있습니다.
예를 들어, 다음과 같은 list가 있다고 하자.
list=[1, 7, 3, 5, 4, 7, 9]
이 리스트를 정렬했을 때
(1) list=[1, 3, 4, 5, 7(1), 7(2), 9
(2) list=[1, 3, 4, 5, 7(2), 7(1), 9
(1)처럼 나오면 안정(Stable) 정렬,
(2)처럼 나오면 불안정(Unstable) 정렬이라고 한다.
안정 정렬의 장점
안정 정렬은 값의 상대적인 순서가 중요한 데이터를 정렬할 때 유용합니다. 예를 들어, 학생들의 성적을 정렬할 때, 성적이 같은 학생들의 순서가 지켜지면 등수를 매기기가 용이합니다.
안정 정렬의 단점
안정 정렬은 다른 정렬 알고리즘에 비해 속도가 느립니다. 특히, 데이터의 크기가 매우 크거나 데이터의 개수가 많을 경우에는 실행 시간이 오래 걸릴 수 있습니다.
안정 정렬의 종류
버블 정렬(Bubble Sort)
버블 정렬은 인접한 두 원소의 대소를 비교하여 조건에 맞지 않으면 서로 교환하는 방식으로 정렬하는 알고리즘입니다.
- 리스트의 첫 번째 자료부터 마지막 자료까지 비교하며 자료의 위치를 교환합니다.
- 마지막 자료까지 비교하고 나면 가장 큰 자료가 맨 뒤로 이동합니다.
- 1~2 과정을 자료의 개수만큼 반복합니다.
- 시간 복잡도: O(n^2)
삽입 정렬(Insertion Sort)
삽입 정렬은 배열의 모든 요소를 돌면서 정렬되어 있지 않은 값들을 정렬된 부분 배열의 적절한 위치에 삽입하는 방식으로 정렬하는 알고리즘입니다.
- 두 번째 자리부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정합니다.
- 선택한 원소를 한 칸씩 뒤로 이동시킨 후 지정한 위치에 넣습니다.
- 1~2 과정을 자료의 개수만큼 반복합니다.
- 시간 복잡도: O(n^2)
병합 정렬(Merge Sort)
병합 정렬은 분할 정복(divide and conquer) 방법을 통해 구현되며, 안정 정렬이 가능한 알고리즘입니다.
- 정렬하고자 하는 배열을 절반으로 나누어 각각 정렬합니다.
- 정렬된 두 배열을 합쳐 하나의 정렬된 배열로 만듭니다.
- 1~2 과정을 재귀적으로 반복하여 전체 배열을 정렬합니다.
- 시간 복잡도: O(nlogn)
In-place Algorithm이란?
In-place Algorithm은 추가 메모리를 사용하지 않고 입력 데이터를 직접 조작하여 정렬하는 알고리즘입니다. 이를 통해 알고리즘의 실행 속도를 높일 수 있습니다. In-place Algorithm의 예시로는 퀵 정렬(Quick Sort), 힙 정렬(Heap Sort) 등이 있습니다.
In-place Algorithm의 장점
In-place Algorithm은 메모리 사용량이 적어 메모리 제한이 있는 환경에서 유용합니다. 또한, 추가적인 메모리를 사용하지 않기 때문에 실행 속도가 빠릅니다.
In-place Algorithm의 단점
In-place Algorithm은 데이터를 조작하므로 입력 데이터가 손상될 가능성이 있습니다. 따라서, 데이터를 복사해두고 원본 데이터는 그대로 두는 안정적인 알고리즘에 비해 데이터의 완전성을 보장하지 못합니다.
