정렬 알고리즘 시간 복잡도

2026. 07. 26

정렬 알고리즘	최선	평균	최악
버블 정렬	`O(n²)`	`O(n²)`	`O(n²)`
선택 정렬	`O(n²)`	`O(n²)`	`O(n²)`
삽입 정렬	`O(n)`	`O(n²)`	`O(n²)`
힙 정렬	`O(n log n)`	`O(n log n)`	`O(n log n)`
병합 정렬	`O(n log n)`	`O(n log n)`	`O(n log n)`
퀵 정렬	`O(n log n)`	`O(n log n)`	`O(n²)`
계수 정렬	`O(n + k)`	`O(n + k)`	`O(n + k)`
기수 정렬	`O(d(n + k))`	`O(d(n + k))`	`O(d(n + k))`
버킷 정렬	`O(n + k)`	`O(n + k)`	`O(n²)`

n은 원소의 개수, k는 값의 범위 또는 버킷의 개수, d는 가장 큰 값의 자릿수이다.