<aside> 📖 Contents
</aside>
데이터를 특정한 기준에 따라서 정렬하기 위해 사용하는 알고리즘이다. 대표적인 알고리즘들의 특징과 시간복잡도를 잘 알아두고 상황에 맞게 사용하자.
문제 상황에 따라 적절한 정렬알고리즘이 공식처럼 사용된다. 데이터의 개수가 적을때, 많지만 데이터의 범위가 한정적일때, 이미 데이터가 정렬되어있는 등 다양한 상황에서 적절한 알고리즘을 공식처럼 사용할 수 있도록 공부해보자.
이번 공부에서는 가장 많이 사용되는 ‘선택정렬’ , ‘삽입정렬’ , ‘퀵정렬’, ‘계수정렬’ 네 가지를 다룬다.
| 정렬 알고리즘 | 평균 시간복잡도 | 공간복잡도 | 특징 |
|---|---|---|---|
| 선택정렬 | O(N^2) | O(N) | 아이디어가 매우 간단하다. |
| 삽입정렬 | O(N^2) | O(N) | 데이터가 거의 정렬되어 있을 때, 가장 빠르다. |
| 퀵정렬 | O(NlogN) | O(N) | 대부분의 경우에 가장 적합하고, 충분히 빠르다. |
| 계수정렬 | O(N+K) | ||
| (K는 데이터 중에서 가장 큰 수) | O(N+K) | ||
| (K는 데이터 중에서 가장 큰 수) | - 데이터의 크기가 한정되어있는 경우에만 사용이 가능하다. |
| 정렬 알고리즘 | 핵심 아이디어 |
|---|---|
| 선택정렬 | 가장 작은 데이터를 ‘선택’해서 정렬되지 않은 데이터중에 가장 앞쪽에 있는 데이터와 위치를 바꾸는 방법 |
| 삽입정렬 | 데이터를 앞에서부터 하나씩 확인하며 데이터를 적절한 위치에 ‘삽입’하는 방법 |
| 퀵정렬 | 기존 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 |
| 계수정렬 | 특정한 값을 가지는 데이터의 개수를 ‘카운트’하는 방법 |
처리되지 않은 데이터를 하나씩 골라 적절한 위치에 ‘삽입’하는 방법이다. 데이터를 하나씩 확인하면서 데이터의 위치가 어디에 적절한지? 매번 계산한다.
선택 정렬에 비해서 구현 난이도가 조금 높은 편이지만, 일반적으로 더 효율적으로 동작한다.
1️⃣ 첫번째 데이터 7은 그 자체로 정렬이 되어있다고 판단하고, 두 번째 데이터인 5부터 판단한다. 5는 어디 위치로 들어갈지 판단한다. 7의 왼쪽으로 들어가거나 오른쪽으로 들어가거나 두 가지 경우에만 고민한다.
2️⃣ 이어서 9는 어느 위치로 들어갈 수 있을지 판단한다. (아래 세 가지 화살표 위치 중에서 한가지를 선택할 수 있다.) 바로 왼쪽의 데이터 7과 비교해서 7보다 작으면 위치를 바꿔주고, 그렇지 않다면 그자리에 머무르도록 한다.
3️⃣ 이어서 0을 판단해보자. 0은 9와 비교해서 바꿔주고, 7과 바꿔주고, 5와 바꿔주는 세번의 위치 교환 작업을 실시하게 된다.
