삽입정렬

앞쪽에 있는 원소들이 이미 정렬돼있다고 가정하고 뒤쪽에 있는 원소를 앞쪽에 있는 원소의 위치 중에서 한 곳으로 들어가도록 만드는 방식으로 동작한다.

• 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용되기 때문에 시간복잡도는 O(N^2)이다.
• 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.
• 최선의 경우 O(N)의 시간 복잡도를 가진다.

퀵정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법으로 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다.

• 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다.

• 가장 기본적인 퀵정렬은 첫 번째 데이터를 기준 데이터(Pivot)으로 설정한다.

• 이상적인 경우 분할이 절반씩 일어난다면 O(NlogN)를 기대할 수 있다.

• 분할이 이루어 질 때마다 이상적인 경우 데이터의 범위가 절반씩 줄어들게 되기 때문에 전체 높이를 확인했을때 logN이라고 볼 수 있다. 그 중에서도 데이터의 범위가 절반씩 줄어들기 때문에 밑이 2인 logN이라고 표현할 수 있다. 데이터의 갯수는 N이기 때문에 너비는 N, 높이는 logN이라서 NlogN을 기대할 수 있다.

• 최악의 경우 O(N^2)의 시간 복잡도를 가진다.

• pivot값을 어떻게 설정하느냐에 따라서 분할이 절반에 가깝게 일어나지 않고 한쪽 방향에 편향된 분할이 발생할 수 있기 때문이다. 이미 정렬된 배열에 대해서 퀵 정렬을 수행하게 되면 분할이 수행되는 횟수가 N번, 분할을 하기 위해서 매번 선형 탐색을 수행해야 하기 때문에 전체 시간복잡도가 N^2가 된다.

계수 정렬

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘이다.

• 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다.
• 데이터의 개수가 N, 데이터(양수)중 최댓값이 K일 때 최악의 경우에도 수행시간 O(N+K)를 보장한다.
• 시간복잡도와 공간복잡도 모두 O(N+K)이다.
• 데이터가 0과 999,999로 단 2개만 존재하는 경우에는 심각한 비효율성을 초래할 수 있다.
• 동일한 값을 가지는 데이터가 여러 개 등장할 대 효과적으로 사용할 수 있다.

---

이진 탐색

1. 순차 탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

2. 이진 탐색

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.

• 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.

• 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2N에 비례한다.

• 이진탐색은 탐색 범위를 절반씩 줄이며 시간 복잡도는 O(logN)을 보장한다.