5. 알고리즘

1️⃣ 버블 정렬

- 양옆에 위치한 두 값을 비교하면서 크기 순으로 정렬

- 뒤에서부터 정렬됨

- 별도의 메모리 공간이 필요하지 않지만, 시간복잡도가 O(n²) 

2️⃣ 선택 정렬

- 배열을 순회하면서 배열의 앞에서부터 차례대로 각 인덱스에 들어갈 값(오름차순이면 최솟값)을 선택해 위치시킴

- 구현이 간단하고 별도의 메모리 공간이 필요하지 않지만, 시간복잡도가 O(n²) 

3️⃣ 삽입 정렬

- 배열을 앞에서부터 순회하면서 정렬된 부분의 적절한 위치에 값을 삽입하는 방식

- 시간복잡도는 O(n²) 

4️⃣ 합병 정렬

- 재귀를 이용하는 분할(배열을 쪼개는 것)정복(분할한 배열을 정렬하면서 하나로 합병하는 것) 알고리즘

- 시간 복잡도는 O(nlogn)

5️⃣ 퀵 정렬

- 합병 정렬과 마찬가지로 분할 정복 알고리즘

- 배열에서 피봇이라는 특정 값을 선택해 피봇보다 작은 값으로 구성된 배열과 피봇보다 큰 값으로 구성된 배열로 분할해 정렬하는 방식

- low, high 둘 다 이동하지 않으면 둘을 교환, 둘이 만나 엇갈리게 된다면 그 부분이 피봇을 기준으로 둘로 나눠지는 기점

- 배열의 크기가 1이하가 될 때까지 반복해서 수행

- 피봇으로 어떤 값을 선택하는지에 따라 퀵 정렬의 성능이 좌우됨! -> 시간복잡도 O(nlogn) ~ O(n²) + 최대한 중간값을 선택해야...

6️⃣ 힙 정렬

- 최대 힙(오름차순)이나 최소 힙(내림차순) 자료구조를 이용해 정렬 수행

- 힙 생성 알고리즘: 특정 노드의 두 자식 노드 중 우선순위가 더 높은 자식 노드와 위치를 교환하는 방식

- 시간 복잡도는 O(nlogn)

(1) 배열을 힙으로 만드는 과정 수행

(2) 생성한 최대 힙에서 삭제 연산을 이용해 정렬 수행(루트 노드 제거-> 마지막 노드를 루트 노드로 -> 힙하게 만들기 -> 삭제연산 수행 반복)

7️⃣ 기수 정렬

- 낮은 자릿수부터 정렬 수행. 비교x

- 시간 복잡도는 (데이터 개수 * 최대 자릿수): O(dn) -> 빠른 편! but 추가 메모리 필요, 정렬할 수 있는 데이터 타입 한정적

8️⃣ 계수 정렬

- 데이터의 개수를 세서 정렬 수행. 비교x

- 데이터의 범위가 0 또는 양의 정수여야 하는 제약조건 있음. 메모리 추가 사용

- 매우 빠름. 특히 데이터의 범위가 작고 값이 중복되는 경우 효과적

- 시간 복잡도는 O(n+k)

(1) 정렬하려는 데이터의 범위를 인덱스로 갖는 빈 배열 생성(n+1길이)

(2) 배열 순회하면서 데이터에 해당하는 계수 배열의 인덱스 값을 1씩 증가시킴

(3) 원본 배열의 마지막 인덱스까지 순회하고 나면, 계수 배열에는 원본 배열의 등장 횟수가 담김

(4) 계수 배열의 인덱스를 순회하면서, 각 숫자를 등장 횟수만큼 결과 배열에 추가

9️⃣ 프림 알고리즘

- 그리디 알고리즘. 임의의 정점을 시작점으로 트리를 확장하면서 최소 신장 트리를 생성하는 방식

- 가중치가 가장 작은 간선으로 연결된 정점을 트리에 추가하면서 최소 신장 트리 생성

🔟 크루스칼 알고리즘

- 그리디 알고리즘. 간선을 오름차순으로 정렬한 뒤 가중치가 낮은 간선을 선택하면서 최소 신장 트리를 생성하는 방식

- 가중치의 오름차순으로 간선을 정렬하는 알고리즘 + 사이클 생성 여부 판단하는 유니온 파인드 알고리즘

1️⃣1️⃣ 다익스트라 알고리즘

- 간선의 가중치가 음수가 아닌 경우, 특정 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘

(1) 시작 정점에서 방문 가능한 정점에 대한 비용을 갱신하고 나머지 정점에 대한 비용은 INF로 설정

(2) 방문하지 않은 정점 중 비용이 가장 적게 드는 정점에 방문 -> 해당 정점을 거쳐 방문할 때 기존보다 적으면 갱신

(3) 모든 정점을 방문할 때까지 방문 비용 갱신

1️⃣2️⃣ 벨만-포드 알고리즘

- 특정 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘 (간선의 가중치가 음수인 경우에도 적용 가능!)

- 하지만 음의 사이클이 있으면 최소 비용이 무한하게 줄어들어서 알고리즘을 적용할 수 없음