1. 정렬 알고리즘 개요
정렬(sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나이다.
숫자가 하나씩 적힌 카드가 10장 있다면, 이 카드를 오름차순으로 정렬해보자. 어떻게 이 카드들을 정렬할 수 있을까?
보통 인간이라면 카드를 훑은 후 순식간에 숫자를 0부터 10까지 구성된 걸 확인하고 순차적을 나열할 것이다.
하지만 컴퓨터에게는 쉬운 작업이 아니다. 컴퓨터는 인간과 다르게 데이터의 규칙성을 직관적으로 알 수 없으며, 어떻게 정렬을 수행할지에 대한 과정을 소스코드로 작성하여 구체적으로 명시해야 한다.
정렬 알고리즘은 다양하게 존재하는데 우선 기본적인 종류는 다음과 같다.
① 간단하지만 느린 방식
- 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) 정도의 성능을 보여준다.
이제 간단히 알아보았으니 추후 포스팅부터 각 정렬 알고리즘이 어떻게 동작하고 코드로는 어떻게 구현할 수 있는지 알아보자.
참고
https://evan-moon.github.io/2018/10/13/sort-algorithm/
https://hongjw1938.tistory.com/27