정렬(Sort)
주어진 데이터(레코드, 배열 등)를 특정 기준(오름차순·내림차순 등)에 따라 순서대로 재배열하는 과정
정렬은 알고리즘의 기본 중 기본으로,
데이터 탐색이나 분석을 효율적으로 하기 위해 꼭 필요한 과정
삽입 정렬(Insertion Sort)
- 이미 정렬된 부분에 새로운 데이터를 순서에 맞게 삽입하여 정렬하는 방식
- 두 번째 원소부터 시작 → 앞의 정렬된 구간과 비교하여 적절한 위치에 삽입
- 구현이 단순하고 직관적
- 데이터가 거의 정렬되어 있으면 빠름
- 자료 이동이 많음
- 평균과 최악 수행 시간 복잡도 : O(n²)
선택 정렬(Selection Sort)
- 전체 원소 중 가장 작은 값(최소값)을 찾아 맨 앞자리로 보내는 과정을 반복
- 1회전 : 최소값 → 첫 번째 위치
2회전 : 두 번째 최소값 → 두 번째 위치 - 교환 횟수가 최소화됨
- 자료 이동은 적지만, 비교 횟수 많음
- 평균과 최악 수행 시간 복잡도 : O(n²)
버블 정렬(Bubble Sort)
- 인접한 두 원소를 비교해 큰 값을 뒤로 보내는 방식
- 1회전마다 가장 큰 값이 맨 뒤로 이동
- 구현 간단
- 비교 및 교환이 많아 비효율적
- 평균과 최악 수행 시간 복잡도 : O(n²)
쉘 정렬(Shell Sort)
- 삽입 정렬을 개선한 방법
- 일정 간격으로 떨어진 원소끼리 부분 정렬을 수행
- 전체 데이터를 여러 개의 부분 리스트로 나누어 각 리스트를 삽입 정렬로 처리 후, 간격을 줄여가며 반복
- 삽입 정렬의 개선형
- 데이터 이동이 적고 평균적으로 빠름
- 간격 선택에 따라 효율성 달라짐
- 평균 수행 시간 복잡도 : O(n¹·⁵)
- 최악 수행 시간 복잡도 : O(n²)
퀵 정렬(Quick Sort)
- 기준값(Pivot)을 중심으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하여 정렬하는 분할 정복 방식
- 원리
- Pivot 선택
- Pivot 기준으로 좌/우 분할
- 각각 재귀적으로 정렬
- 평균적으로 매우 빠름
- 정렬 중간에 원소 교환만 수행 → 추가 공간 적음
- 평균 수행 시간 복잡도 : O(n log n)
- 최악 수행 시간 복잡도 : O(n²)
힙 정렬(Heap Sort)
- 완전 이진 트리 형태의 힙(Heap) 자료 구조를 이용한 정렬
- 최대 힙 : 루트가 가장 큰 값
- 루트 제거 후 마지막 노드와 교환 → 재정렬 반복
- 정렬 중에 추가 메모리 불필요
- 항상 일정한 수행 시간 보장
- 평균과 최악 수행 시간 복잡도 : O(n log n)
2-Way 합병 정렬(Merge Sort)
- 이미 정렬된 두 개의 리스트를 하나로 합치는 과정을 반복하는 정렬
- 원리
- 리스트를 반으로 분할
- 각각 정렬 후 합병
- 병합 과정에서 항상 순서 유지
- 평균과 최악 수행 시간 복잡도 : O(n log n)
기수 정렬(Radix Sort, = Bucket Sort)
- 자릿수(Digit)를 기준으로 낮은 자릿수부터 차례로 정렬하는 방식
- 각 자릿수에 따라 버킷에 분배 후, 버킷 순서대로 다시 수집
- 비교 연산을 수행하지 않음
- 키 값이 일정 범위일 때 매우 효율적
- 정렬 속도가 일정함
- 평균과 최악 수행 시간 복잡도 : O(dn)
'정보처리기사' 카테고리의 다른 글
| 정보처리기사 실기 - 연계 메커니즘 (0) | 2025.11.03 |
|---|---|
| 정보처리기사 실기 - 통합 구현 (0) | 2025.11.02 |
| 정보처리기사 실기 - 이진 트리 (0) | 2025.11.02 |
| 정보처리기사 실기 - 트리(Tree) (0) | 2025.11.02 |
| 정보처리기사 실기 - 자료 구조 (0) | 2025.11.02 |