정보처리기사 필기 이론 학습 | 모두의 문제집

이하의 설명과 배열 추적은 오름차순 정렬의 대표적인 배열 구현을 기준으로 한다. 퀵 정렬의 구체적인 추적은 마지막 원소를 피벗으로 삼아 피벗을 최종 위치에 두는 로무토 분할, 기수 정렬은 낮은 자릿수부터 처리하는 LSD 방식을 사용한다. 퀵·힙·병합 정렬은 원소의 대소를 비교하는 비교 정렬이고, 기수 정렬은 키의 자릿값을 이용해 분배하는 비비교 정렬이다.

네 알고리즘은 한 단계가 끝났을 때 보장되는 상태부터 구분하면 혼동이 줄어든다.

알고리즘	한 단계의 핵심 동작	단계 뒤 보장되는 상태
퀵 정렬	피벗을 기준으로 한 번 분할	피벗의 최종 위치가 확정됨. 양쪽 부분 배열 자체는 아직 정렬되지 않을 수 있음
힙 정렬	최대 힙의 루트와 힙의 마지막 원소를 교환	현재 최댓값이 정렬 완료 구간의 맨 앞에 확정됨
병합 정렬	이미 정렬된 두 구간을 병합	두 구간을 합친 더 큰 구간이 정렬됨. 개별 원소의 전체 최종 위치는 마지막 병합 전까지 달라질 수 있음
LSD 기수 정렬	현재 자릿수로 안정적으로 분배·수집	지금까지 처리한 낮은 자릿수들의 순서가 맞음. 가장 높은 자릿수까지 끝나야 전체 정렬 완료

시험 직전 요약장

고급 정렬: 퀵·힙·병합·기수

헷갈리는 개념

대표 계산·예제

내 최근 연습 오답