<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는 데이터 중에서 가장 큰 수) | - 데이터의 크기가 한정되어있는 경우에만 사용이 가능하다. |
| 정렬 알고리즘 | 핵심 아이디어 |
|---|---|
| 선택정렬 | 가장 작은 데이터를 ‘선택’해서 정렬되지 않은 데이터중에 가장 앞쪽에 있는 데이터와 위치를 바꾸는 방법 |
| 삽입정렬 | 데이터를 앞에서부터 하나씩 확인하며 데이터를 적절한 위치에 ‘삽입’하는 방법 |
| 퀵정렬 | 기존 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 |
| 계수정렬 | 특정한 값을 가지는 데이터의 개수를 ‘카운트’하는 방법 |
특정한 조건이 부합할 때만 사용하는 정렬 알고리즘
O(N+K)를 보장함1️⃣ 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성
정렬할 데이터: 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 라면, 가장 작은데이터가 0, 가장 큰 데이터는 9 이므로 0부터 9까지가 모두 담길 수 있도록 배열을 초기화해서 만들어놓자. 인덱스 번호는 ‘값’을 의미한다. 그래서 각 인덱스 값이 몇 번 등장했는지 계수를 배열 안에 넣는다.
2️⃣ 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다.
