정렬 알고리즘 중 최악의 경우를 가정할 때 시간복잡도가 다른 것은?

1. 1

   삽입 정렬(Insertion sort)

   오답 이유삽입 정렬은 역순 입력에서 각 원소가 앞의 거의 모든 원소와 비교·이동되어 O(n²)이다.
2. 2

   쉘 정렬(Shell sort)

   오답 이유시험에서 전제하는 기본 간격 감소 방식의 쉘 정렬은 최악에 O(n²)까지 갈 수 있다.
3. 3

   버블 정렬(Bubble sort)

   오답 이유버블 정렬은 역순 입력에서 인접 비교를 약 n(n-1)/2회 수행해 O(n²)이다.
4. 4

   힙 정렬(Heap sort)

   정답 근거힙 구성과 n번의 삭제·재정렬이 각각 로그 높이 안에서 처리되어 최악에도 O(n log n)이다.