정렬 알고리즘 정리
이 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있을 수 있고, 피드백은 환영합니다.
제자리 정렬(In-place Sort)
- 정렬 대상이 되는 원래 배열 내부에서 원소들의 위치를 서로 바꾸는 방식으로 정렬하는 알고리즘
- 추가적인 메모리 공간이 필요하지 않거나, 상수 크기의 추가 공간만 필요로 한다
- 예시: 버블 정렬, 선택 정렬, 삽입 정렬, 힙 정렬, 쉘 정렬, 퀵 정렬 (퀵 정렬은 재귀 호출로 인해 O(log n) 스택 공간이 필요하지만, 일반적으로 제자리 정렬로 간주된다)
병합 정렬, 기수 정렬, 카운팅 정렬, 버킷 정렬은 제자리 정렬이 아니다.
안정 정렬(Stable Sort)
중복된 키값을 가진 원소들이 정렬 전후에 순서가 유지되는 정렬 알고리즘을 뜻한다.
예를 들어 [1, 7(1), 2, 4, 7(2), 3]이란 배열이 있다고 하자. 7(1)과 7(2)는 키값이 7로 동일하지만, 7(1)은 7(2)보다 먼저 등장한다. 정렬 이후에도 7(1)이 7(2)보다 먼저 등장한다면, 이 정렬 알고리즘은 안정 정렬이다.
삽입 정렬, 병합 정렬, 버블 정렬, 계수 정렬이 안정 정렬에 속하고, 선택 정렬, 힙 정렬, 쉘 정렬, 퀵 정렬은 불안정 정렬에 속한다.
선택 정렬(Selection Sort)
제자리 정렬, 불안정 정렬
최선/최악/평균 모두 $O(n^2)$의 시간 복잡도
첫 번째 원소를 선택한 후, 나머지 원소들 중에서 가장 작은 원소를 찾아 첫 번째 원소와 교환한다. 그 다음 두 번째 원소를 선택한 후, 나머지 원소들 중에서 가장 작은 원소를 찾아 두 번째 원소와 교환한다. 이 과정을 반복하여 모든 원소가 정렬될 때까지 진행한다.
장점
- 구현이 간단하다.
- 데이터 교환 횟수가 각 회전당 1번으로 적다.
단점
- 데이터의 상태(정렬 여부)와 상관없이 무조건 O(n^2)의 시간 복잡도를 가진다.
- 불안정 정렬이다.
삽입 정렬(Insertion Sort)
제자리 정렬, 안정 정렬
최선의 경우 O(n), 최악의 경우 O(n^2), 평균 O(n^2)의 시간 복잡도
두 번째 원소부터 시작하여 각 원소를 그 이전의 원소들과 비교하여 적절한 위치에 삽입하는 방식으로 정렬한다.
장점
- 구현이 단순하고 쉽다.
- 데이터가 거의 정렬되어 있는 경우 효율적[O(n)]이다.
단점
- 원소의 이동이 많다.
- 데이터가 역순으로 정렬된 경우 최악의 성능을 보인다.
버블 정렬(Bubble Sort)
제자리 정렬, 안정 정렬
최선/최악/평균 모두 O(n^2)의 시간 복잡도, 단 조기 종료 플래그 사용 시 이미 정렬된 데이터 한정 O(n)
인접한 원소들을 비교하여 순서가 잘못된 경우 서로 교환하는 방식으로 정렬한다. 이 과정을 반복하여 모든 원소가 정렬될 때까지 진행한다.
장점
- 구현이 매우 간단하고 코드가 직관적이다.
단점
- 최선/최악/평균 모두 O(n^2)의 시간 복잡도를 가지기에 비효율적이다.
- 조기 종료 플래그를 사용하고 이미 정렬된 데이터에 한정하여 O(n)의 시간 복잡도를 가질 수 있다.
퀵 정렬(Quick Sort)
제자리 정렬, 불안정 정렬
최선/평균 O(n log n), 최악 O(n^2)의 시간 복잡도
퀵 정렬은 분할 정복 방법으로 정렬하는 알고리즘이다.
임의의 피봇(원소)을 선택하고 피봇의 왼쪽에는 피봇보다 작은 원소들, 피봇의 오른쪽에는 피봇보다 큰 원소들을 두면 피봇의 위치가 정해진다는 점으로 정렬을 수행한다.
장점
- 평균적으로 O(n log n)의 시간 복잡도를 가진다.
- 배열의 특정 구간 내에서 순차적으로 데이터를 접근하며 정렬하므로 캐시 히트율이 높다.
단점
- 피봇을 어떻게 선택하냐에 따라 시간 복잡도가 다르다.
- 순차 접근이 아닌 임의 접근이기에 연결 리스트에서는 비효율적이다.
병합 정렬
비제자리 정렬, 안정 정렬
최선/최악/평균 모두 O(n log n)의 시간 복잡도
병합 정렬은 분할 정복 방법으로 정렬하는 알고리즘이다.
더 이상 쪼갤 수 없을 때 까지 반으로 나눈 뒤, 다시 합치면서 정렬한다.
- 분할 : 배열을 반으로 나눈다. 이 과정을 배열의 크기가 1이 될 떄까지 재귀적으로 반복한다.
- 정복 : 쪼개진 작은 배열들을 정렬한다. 원소가 1개인 상태에서 시작하므로, 처음에는 두 원소를 비교하여 정렬하는 것부터 시작한다.
- 병합 : 정렬된 두 개의 작은 배열을 하나의 정렬된 배열로 합친다. 두 배열의 맨 앞 원소부터 비교하며, 더 작은 값을 새로운 임시 배열에 순서대로 채워 넣는 방식으로 동작한다.
장점
- 최선/최악/평균 모두 O(n log n)의 시간 복잡도를 가진다.
- 순차 접근이기에 연결 리스트를 정렬할 때 효율적이다.
단점
- 배열을 쪼개고 합치는 과정에서 추가적인 메모리 공간 O(n)이 필요하다.
힙 정렬
제자리 정렬, 불안정 정렬
최선/최악/평균 모두 O(n log n)의 시간 복잡도
힙 정렬은 힙 자료구조를 이용하여 정렬하는 알고리즘이다. 전체 배열을 최대 힙으로 만든 뒤, 루트에 있는 최댓값을 맨 뒤로 보내고, 남은 원소들로 다시 힙을 구성하는 과정을 반복하여 정렬한다.
장점
- 최선/최악/평균 모두 O(n log n)의 시간 복잡도를 가진다.
- 전체를 다 정렬하지 않고, 가장 큰 값 몇 개만 필요할 때 효율적이다.
단점
- 매번 힙 트리를 재구조화하는 과정에서 인덱스가 튀기 때문에 캐시 적중률이 떨어진다. 그래서 퀵 정렬이나 병합 정렬보다 느린 편이다.
참고