CS 부수기 - 알고리즘 (정렬 : 안정성) 편
0. 정렬 알고리즘이란
이번 편은 정렬 알고리즘(Sorting Algorithm)과 안정성에 대해 알아보려고 한다.
전 편에서 다룬 탐색 알고리즘은 다음 링크를 확인하면 된다.
정렬 알고리즘의 정의는 위키피디아에 따르면 다음과 같다.
Sorting Algorithm : 컴퓨터 과학과 수학에서 정렬 알고리즘은 원소들을 번호순이나 사전순과 같이 일정한 순서대로 열거하는 알고리즘을 의미한다. 다른 알고리즘 혹은 최적화 시에 매우 중요하며, 가시성과 가독성을 향상시킨다.
정렬 알고리즘에는 다음과 같은 알고리즘들이 있다.
- Selection Sort Algorithm : 선택 정렬 알고리즘
- Insertion Sort Algorithm : 삽입 정렬 알고리즘
- Bubble Sort Algorithm : 버블 정렬 알고리즘
- Quick Sort Algorithm : 퀵 정렬 알고리즘
- Merge Sort Algorithm : 합병 정렬 알고리즘
이러한 정렬 알고리즘을 구성할 때 고려할 사항은 다음과 같다.
- 시간 복잡도 - Time Complexity
- 메모리 사용량 - Memory Usage
- 안정성 - Stability
특히나 안정성(Stability)은 매우 중요하다.
일반적으로 안정성은 반복되는 요소를 정렬시킬 때, 순서를 결정할 시 데이터의 일부만 검사하기 때문에 중요한데, 예를 들어 설명해보려고 한다.
1. 정렬 알고리즘에서 안정성
다음 내용은 geeksforgeeks의 포스팅 내용을 참고하여 작성하였다.
일반적으로, 키값만 가지는 리스트를 정렬할 경우에는 안정성을 고려할 필요가 없다.
하지만, 리스트가 키 - 속성을 가지고 정렬할 경우, 이러한 안정성은 매우 중요해진다.
안정성을 고려하지 않을 경우, 리스트를 정렬할 때 이전의 정렬 기준을 무시해버리기 때문이다.
예시를 통해서 더 자세히 알아보자.
다음과 같은 형태를 가지는 학생 리스트가 있다고 가정하자.
정렬되어 있지 않은 학생 리스트
먼저 이름을 사전순으로 정렬을 하면 다음과 같다.
사전순으로 이름 정렬
이름을 사전순으로 정렬 후, 학생이 소속된 반으로 재정렬을 하려고 하는데, 이 때 안정성을 고려하지 않고 정렬하면 다음과 같이 정렬된다.
안정성 고려하지 않은 정렬
학생이 소속되어 있는 반을 기준으로 재정렬하였지만, 기존의 이름의 사전순 정렬은 무시한 채 정렬이 된것을 확인할 수 있다.
우리는 이러한 정렬 형태를 “비안정성 정렬” 이라고 부른다.
하지만 우리가 원하는 정렬은 기존의 이름의 사전순 정렬과 소속 반 정렬이 같이 이루어진 정렬이다.
즉, 안정성이 고려된 형태의 정렬을 원하는 것이다.
안정성을 고려하여 정렬하면 다음과 같이 정렬이 이루어지게 된다.
안정성이 고려된 정렬
이와 같이 말이다.
이러한 안정성이 고려되지 않는 정렬과 고려된 정렬은 다음과 같은 정렬들이 있다.
- 불안정 정렬 예 : 선택 정렬, 퀵 정렬, 힙 정렬
- 안정 정렬 예 : 버블 정렬, 삽입 정렬, 병합 정렬, 계수 정렬
그렇다면 본격적으로 정렬 알고리즘에 대해서는 다음 편을 통해 알아보자.
Adios