알고리즘 개념 총정리 - 정렬

a) 버블 정렬(Bubble Sort)

- 인접한 요소끼리 크기 비교를 하며 swap과정을 통해 정렬한다.

- 더이상 swap이 발생하지 않는 상태까지 정렬과정을 반복한다. 

- O(n^2)의 시간복잡도를 가진다.

 

b) 삽입 정렬(Insertion Sort)

- 가장 좌측의 요소를 기준으로 다른 요소와 비교하며 swap과정을 통해 정렬한다.

- 기준 요소보다 작은 요소들은 기준요소의 좌측에, 큰 요소들은 기준요소의 우측에 정리하는 과정을 반복한다.

- O(n^2)의 시간복잡도를 가진다.

 

c) 선택 정렬(Selection Sort)

- 가장 좌측 요소의 위치를 포인터로, 포인터가 가리키는 요소보다 작은 요소를 찾아 swap하며 정렬한다.

- swap이 한번 일어날 때마다, 포인터의 위치는 오른쪽으로 한칸씩 증가하며, 정렬 과정을 반복한다.

- O(n^2)의 시간복잡도를 가진다.

 

d) 병합 정렬(Merge Sort)

- 분할정복 알고리즘에 포함

- 배열의 요소를 최소단위(길이 1의 배열)로 쪼개어 재구성한 후,

  각 배열에 포인터를 두어 요소간의 크기 비교를 통해 재정렬 후 병합하는 과정을 반복한다.

- O(n log n)의 시간복잡도를 가진다.

 

e) 빠른 선택(Quick Selection)

- 배열의 n번째 크거나 작은 요소를 찾기 위한 알고리즘

- 특정 요소를 기준(pivot)으로 지정하여 기준요소보다 작은 요소는 좌측에, 큰 요소는 우측에 정렬한다.(파티셔닝 기법)

- 배열의 가장 좌측과 우측에 포인터를 두어 요소의 값을 비교 및 swap하는 과정을 반복하며 정렬한다.

- Quick Selection은 한번 진행하였다고 모든 요소가 정렬되는 것은 아니다. 하지만, 찾고있는 요소의 위치를 추측할 수 있다.

- pivot을 기준으로 좌측 또는 우측에 찾는요소가 존재하므로, 탐색의 대상이 줄어든다는 장점을 갖는다. 

- pivot이 배열의 최소값 또는 최대값으로 선택된 경우, 이를 최악의 경우로 판단하며 O(n^2)의 시간복잡도를 가진다.

- pivot이 배열의 Median(중간 값)에 근사한 값인 경우, 이를 최적의 경우로 판단하며 O(log n)의 시간복잡도를 가진다.

- 빠른선택 알고리즘은 최악의 경우와 최적의 경우를 기반하여 평균적으로 O(n)의 시간복잡도를 가진다.

 

f) 빠른 정렬(Quick Sort)

- 빠른 선택 알고리즘과 동일하게 파티셔닝 기법을 사용한 정렬 알고리즘이다.

- pivot을 기준으로, 좌/우측 요소에 재귀적으로 Quick Sort를 적용하며 정렬한다.

- pivot이 배열의 최소값 또는 최대값인 경우, 이를 최악의 경우로 판단하며 O(n^2)의 시간복잡도를 가진다.

- pivot이 Median에 근사한 값인 경우, 이를 최적의 경우로 판단하며 O(n log n)의 시간복잡도를 가진다.

- 최적의 경우, 파티셔닝 과정을 O(log n) 그리고 좌/우측 요소에 대한 재귀적 수행을 O(n)의 시간복잡도를 가진다.

 

g) 힙 정렬(Heap Sort) 

- 우선순위 큐(= heap를 이용하여 정렬한다.

- Heap의 성질(완전 이진트리, Min/Max heap)을 이용하여 배열의 요소를 정렬하는 방식이다.

- heapify의 과정은 O(n)의 시간복잡도를 가진다.

- heappop의 과정은 O(1)의 시간복잡도를 가진다. (root 노드이므로)

- heappush의 과정은 O(log n)의 시간복잡도를 가진다. (완전 이진트리이므로 탐색의 갯수고 50%씩 감소)

 

h) 계수 정렬(Counting Sort)

- 배열의 요소를 계수로 이용하여 정렬하는 방법 

- 가장 큰 요소와 가장 작은 요소의 차이만큼 길이를 갖는 배열을 생성하고, 배열의 요소를 index로 활용하여 그 갯수를 표시한다.

- O(n + k)의 시간복잡도를 가진다.

- K는 배열의 가장 큰 요소로, K의 크기에 따라 계수를 기록할 배열의 크기가 정해지고 탐색을 위한 반복문의 횟수가 정해진다.

 

i) 기수 정렬(Radix Sort)

- 배열 요소의 자릿수를 이용하여 정렬하는 방법

- Counting Sort의 단점(계수 배열의 크기가 input에 따라 좌우되는 것)을 보완하는 정렬 알고리즘이다.

- 요소의 자릿수를 이용하므로, 기수의 범위가 0 ~ 9로 길이 10의 배열만을 이용한다. (K = 10으로 고정)

- O(w * (n + k))의 시간복잡도를 가진다.

- w는 가장 큰 요소의 자릿수, n은 배열의 길이, k는 10으로 고정된 값이다.

- ex) 가장 큰 요소가 3자리 수인 배열의 경우, O(3 * (n + 10))의 시간복잡도를 가지므로, O(n)의 시간복잡도를 갖는다.

- ex) w = 100, n = 10인 경우, w가  n^2과 동일한 값이므로 O(n^2)의 시간복잡도를 갖는다. 

 

j) 정렬 알고리즘 별 시간복잡도 정리 

1. Bubble Sort → O(n^2)

2. Insertion Sort → O(n^2)

3. Selection Sort → O(n^2)

4. Merge Sort → O(n log n)

5. Quick Sort → 최악의 경우: O(n^2), 최적의 경우: O(n log n), 평균의 경우: O(n) 

6. Heap Sort → heapify: O(n), heappop: O(1), heappush: O(log n)

7. Counting Sort → O(n + k)  

8. Radix Sort → O(w * (n + k))