728x90
반응형
| 정렬 알고리즘 | 정의 |
| 버블 (bubble) | 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 |
| 선택 (selection) | 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 |
| 삽입 (insertion) | 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 |
| 퀵 (quick) | pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 |
| 병합 (merge) | 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식 |
| 기수 (radix) | 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식 |
📌 병합 정렬이란?
- 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식
- 분할 정복(divide and conquer) 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘
- 시간 복잡도 : O(nlogn)
📌 병합 정렬 과정
➡️ 최초에는 8개의 그룹으로 나눈고 2개씩 그룹을 합치며 오름차순으로 정렬하며 반복한다
🍒 2개의 그룹을 병합하는 과정
✔️ 투 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합
✔️ 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1 칸 이동
✅ 다음 게시글에서 예제 문제로 더 자세히 이해해보도록 하겠습니다!
[JAVA][Baekjoon] 1517번 버블 소트 🌟🌟🌟
https://www.acmicpc.net/problem/1517 📌 접근 방식제목은 버블 소트이지만, N의 최대 범위가 500,000이므로 버블 정렬을 이용한다면 시간 초과가 발생한다!➡️ 그래서 O(nlogn)의 시간 복잡도를 가진 병합
nyeroni.tistory.com
728x90
반응형
'CS > 알고리즘' 카테고리의 다른 글
| [알고리즘] 깊이 우선 탐색 : DFS(Depth-First-Search) (0) | 2025.01.04 |
|---|---|
| [알고리즘] 기수 정렬(Radix Sort)이란? (0) | 2025.01.03 |
| [알고리즘] 퀵 정렬(Quick Sort)이란? (1) | 2025.01.02 |
| [알고리즘] 삽입 정렬(Insertion Sort)이란? (0) | 2025.01.02 |
| [알고리즘] 선택 정렬(Selectio Sort)이란? (2) | 2025.01.02 |