SHELL · QUICK

삽입 개선판과 분할정복 대표 — 키워드만 챙기기

셸 정렬 (Shell)O(n^1.5)

간격(gap)을 크게 두고 정렬하다 점점 줄여 마지막 간격 1(=삽입)로 마무리. 삽입 정렬 개선판 키워드.

퀵 정렬 (Quick)O(n log n)

피벗 기준 작은 건 왼쪽·큰 건 오른쪽으로 분리 후 재귀. 분할정복 대표. 최악 O(n²).

👤

반장 분리법 — 반장(피벗)보다 작으면 왼쪽, 크면 오른쪽. 각 그룹에서 또 새 반장으로 반복 → 평균 O(n log n).

함정 차단

'퀵 정렬의 최악은?' → O(n²) (피벗을 정렬된 끝값으로 잡았을 때). 평균과 최악이 다른 게 퀵의 특징.