<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️⃣ 처리되지 않은 데이터 중 가장 작은 0 을 선택해서 가장 앞 7과 바꾼다.
2️⃣ 처리되지 않은 데이터 중 가장 작은 데이터 1을 선택하고 가장 앞의 데이터 5랑 바꾼다.
3️⃣ 처리되지 않은 데이터 중 가장 작은 2를 맨 앞 데이터 9랑 바꾼다.
