Bubble / Selection / Insertion 정렬의 설명은 여기를 참조
Shell 정렬의 설명은 여기를 참조
Merge 정렬의 설명은 여기를 참조
Quick 정렬의 설명은 여기를 참조
Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조
Counting 정렬의 설명은 여기를 참조
Radix 정렬의 설명은 여기를 참조
Bucket 정렬의 설명은 여기를 참조
Topological 정렬의 설명은 여기를 참조
1. 정렬 알고리즘 개요
지금까지의 포스팅을 통해 다양한 자료구조를 배열 / 리스트 기반으로 구현할 수 있다는 것을 확인하였으므로 이제 그 데이터를 다루는 방법에 대해 좀 더 알아보자.
가장 기본적으로 자료 구조에 정의된 데이터들을 어떻게 정렬할 수 있는지에 대해서 알아보자. 정렬 알고리즘은 다양하게 존재하는데 우선 기본적인 종류는 다음과 같다.
① 간단하지만 느린 방식
- Bubble Sort
- Selection Sort
- Insertion Sort
② 약간 복잡하지만 빠른 방식
- Shell Sort
- Merge Sort
- Quick Sort
- Heap Sort
③ 아주 빠르지만 제한적으로만 사용가능한 방식
- Counting Sort
- Radix Sort
- Bucket Sort
④ 기타 필요에 따라 사용되는 방식
- Topological Sort
이제부터 위와 같은 모든 정렬 방식에 대해 하나씩 알아보는 포스팅을 진행할 예정이다. 그 전에 정렬 알고리즘의 성격에 따라 좀 더 이해해보도록 하자.
정렬 알고리즘은 그 실행 방법에 따라 비교식(Comparative) / 분산식(Distribute) 정렬이 있다.
비교식 정렬은 정렬을 수행하면서 두 개의 데이터를 서로 비교하여 필요하면 교환하는 방식으로 실행하며, 분산식 정렬은 정렬할 데이터를 부분적으로 나누어 분해한 뒤 다시 그 집합을 정렬하고 합치면서 전체를 정렬하는 방식이다.
정렬 알고리즘은 정렬 장소에 따라서도 분류되는데 내부(Internal) / 외부(External) 정렬이 있다.
내부 정렬은 정렬 자료를 메인 메모리에 저장하며 정렬하여 속도가 빠르지만 용량에 따라 수행가능한 수준이 제한적이다. 외부 정렬은 정렬 자료를 보조 기억장치에서 정렬하며 대용량이므로 큰 데이터를 정렬할 수 있지만 속도는 제한적이다.
정렬 알고리즘은 저장되는 방식에 따라 Stable / Unstable 정렬로 구분된다.
Stable 정렬은 진행되면서 같은 수준의 순서를 갖는 객체를 정렬할 때는 원래의 순서를 바꾸지 않는다는 말이다. 예를 들어 객체 A와 B는 순서상으로 완전히 동일하다면 정렬이 끝난 뒤와 정렬 전의 A, B 의 순서는 유지되는 경우를 의미한다. Unstable 정렬은 해당 내용이 반드시 유지되지 않을 수 있는 모든 정렬을 의미한다.
정렬 알고리즘은 메모리 사용방식에 따라 In Place / Not In Place 정렬로 구분된다.
In Place 정렬은 데이터를 정렬 시 입력된 n 사이즈의 크기 배열 공간이 추가로 필요하지 않은 경우이며, Not In Place는 정렬 시에 기존 데이터가 저장된 배열 외에 추가적인 공간을 더 필요로 하는 경우를 의미한다.
2. 정렬 알고리즘의 성능
이와 같이, 정렬 알고리즘의 종류와 그 성격의 분류에 대해 알아보았으니 정렬 알고리즘의 성능에 대해서도 알아보자. 알고리즘에 따라 자체적으로 어느 정도의 성능을 내느냐는 구현 방식에 따라서도 차이가 있지만 기본적으로 정렬되지 않은 상태의 데이터가 어떤 상태이냐에 따라서도 다르다.
간단하게 아래의 애니메이션을 보자.
이 내용은 아래의 사이트에서 간단하게 확인해볼 수 있다.
www.toptal.com/developers/sorting-algorithms
Sorting Algorithms Animations
Animation, code, analysis, and discussion of 8 sorting algorithms on 4 initial conditions.
www.toptal.com
위의 애니메이션을 통해서도 알 수 있지만 대부분의 경우 Heap / Merge / Quick 정렬이 매우 빠르다. 하지만 일부 특수 상황에 따라 Bubble / Insertion / Selection 정렬이 더 빠를 수도 있다.
실제로 정렬 알고리즘의 수행 시간은 평균적인 수준과 최악의 수준에 따라 아래와 같은 표로 나타낼 수 있다.
| 정렬 방식 | 평균 시간복잡도 | 최악 시간복잡도 | 메모리 | Stable 여부 | In-Place 여부 |
| Bubble 정렬 | O(n^2) | O(n^2) | O(1) | O | O |
| Selection 정렬 | O(n^2) | O(n^2) | O(1) | X | O |
| Insertion 정렬 | O(n^2) | O(n^2) | O(1) | O | O |
| Shell 정렬 | O(nlogn) | O(n^2) | O(1) | X | O |
| Merge 정렬 | O(nlogn) | O(nlogn) | O(n) | O | X |
| Quick 정렬 | O(nlogn) | O(n^2) | O(1) | X | O |
| Heap 정렬 | O(nlogn) | O(nlogn) | O(1) | X | O |
위 테이블을 보면 대략적인 각 알고리즘들에 대한 성질을 이해할 수 있다. 일반적으로 Quick 정렬이 가장 빠르다고 알려져 있는데 테이블 상으로 최악의 경우 O(n^2)의 시간복잡도를 갖는 것을 알 수 있다.
그러나, 이 경우는 Quick 정렬을 수행 시 설정하는 Pivot 값을 최소 혹은 최대값으로 잡게 되는 경우 그러하며, 이를 피하기 위해 랜덤으로 설정하거나 Media-Of-Three Partitioning 등의 기법을 통해 성능을 끌어올릴 수 있다. 일반적으로 가장 성능이 좋다.
위의 테이블에서 기타 다른 정렬들의 정보까지는 넣지 않았는데 이는 추후 포스팅을 통해 각 정렬에 대해 알아보도록 하자.
Java JDK는 배열을 정렬할 때, 간단히 sort 메소드를 호출하면 되는데 내부적으로 어떤 방식을 사용할까? Java JDK에서는 Dual-Pivot Quick 정렬 방식을 사용한다. 이는 One-Pivot Quick 정렬에 비해 빠르며 O(nlogn) 정도의 성능을 보여준다.
이제 간단히 알아보았으니 추후 포스팅부터 각 정렬 알고리즘이 어떻게 동작하고 코드로는 어떻게 구현할 수 있는지 알아보자.
'자바 프로그래밍 > 자료구조(Data Structure)' 카테고리의 다른 글
| 자료구조 - 정렬 2 (Shell) (0) | 2020.11.09 |
|---|---|
| 자료구조 - 정렬 1 (Bubble / Selection / Insertion) (0) | 2020.11.07 |
| 자료구조 - 세그먼트 트리(Segment Tree)2 - 느린 전파 (0) | 2020.11.02 |
| 자료구조 - 트라이(Trie) (6) | 2020.10.25 |
| 자료구조 - 그래프(Graph) (0) | 2020.10.20 |
