시험 직전 요약장

정렬(Sort)은 원소를 키의 순서에 맞게 재배치하되, 정렬 전후에 원소의 종류와 개수가 같아야 하는 연산이다. 이하의 예시는 배열을 오름차순으로 정렬하는 표준 구현을 기준으로 한다.

정렬 문제에서는 실행 결과만 보지 말고 다음 성질을 함께 구분해야 한다.

• 안정 정렬(Stable Sort): 키가 같은 원소들의 입력 순서를 정렬 후에도 보존한다.
• 제자리 정렬(In-place Sort): 입력 배열 이외에 원소 수에 비례하는 추가 저장 공간을 사용하지 않는다. 일반적으로 O(1)의 보조 공간만 사용한다.
• 적응성(Adaptiveness): 입력이 이미 정렬되어 있거나 거의 정렬되어 있을 때 작업량이 줄어드는 성질이다.
• 회전(Pass): 미정렬 구간을 한 번 처리하는 단위다. 알고리즘과 진행 방향에 따라 한 회전 뒤 확정되는 영역이 다르다.

같은 빅오 표기가 붙어 있어도 비교 위치, 이동 횟수, 안정성, 입력 상태의 영향은 서로 다르다.

삽입 정렬에서 “앞쪽 구간이 정렬되었다”는 말은 그 구간 내부의 순서가 맞다는 뜻이다. 예를 들어 2회전 뒤의 [2, 4, 5]는 정렬되어 있지만, 뒤에 있는 1이 앞으로 들어올 수 있으므로 세 원소의 전체 최종 위치가 확정된 것은 아니다.