정보처리기사 알고리즘 — 정렬·탐색·해싱 핵심 특징

정렬 알고리즘은 수행 위치에 따라 갈린다. 주기억장치 내에서 이루어지는 내부 정렬에는 삽입 정렬, 선택 정렬, 셸 정렬, 버블 정렬, 퀵 정렬, 힙 정렬 등이 있다. 데이터가 많아 주메모리에 모두 올릴 수 없을 때 보조 기억장치를 이용하는 외부 정렬에는 캐스케이드 머지 소트, 밸런스드 머지 소트, 폴리페이즈 머지 소트 등 머지 소트 계열이 속한다.

버블 정렬은 인접한 두 데이터를 비교하여 크기에 따라 위치를 바꾸는 방식으로, 거품이 뜨듯 한 번의 반복마다 가장 큰 값이 배열 끝으로 이동한다. 퀵 정렬은 기준이 되는 분할 원소(피벗)를 정해 데이터를 작은 부분으로 나누어 정렬하는 분할 정복 방식이다. 분할 원소는 반드시 첫 번째 키일 필요 없이 중간 값이나 무작위 값 등 임의로 선택할 수 있으며, 재귀 호출을 위해 스택 공간을 사용하고 최악의 경우 시간 복잡도가 O(n²)이 될 수 있다. 힙 정렬은 배열을 힙(완전이진트리)으로 구성해 가장 큰 값을 루트에서 제거하고 남은 데이터로 힙을 재구성하는 과정을 반복하며, 시간 복잡도는 최선·평균·최악 모두 O(n log n)으로 일정하다.

탐색에서는 이진 탐색이 핵심이다. 이진 탐색(Binary Search)은 정렬된 데이터에서 중간값과 찾는 값을 비교해 탐색 범위를 매번 절반으로 줄이는 방식으로, 데이터 수가 N개일 때 최대 log₂N번의 비교로 탐색을 마친다. 피보나치 수열에 따라 다음 대상을 선정하는 것은 별도의 피보나치 탐색이지 이진 탐색의 특징이 아니다. 해싱에서 충돌이 일어나면 그 다음 버킷들을 차례로 하나씩 검색해 최초로 나오는 빈 버킷에 데이터를 저장하는 방식은 선형 개방 주소법이다. 이차 조사법은 제곱 간격으로 건너뛰고, 재해싱은 해시 함수를 바꾸는 방식이다.