다음의 정렬 알고리즘들 중 N개의 데이터를 정렬하는 데 최악의 경우에 … | [9급 서울시 컴퓨터일반] 14년 1회차 기출문제 상세 페이지
1[9급 서울시 컴퓨터일반] 14년 1회차
다음의 정렬 알고리즘들 중 N개의 데이터를 정렬하는 데 최악의 경우에 비교 횟수가 O(N logN)인 알고리즘으로 옳은 것은?
1
병합 정렬(Merge Sort)
2
퀵 정렬(Quick Sort)
3
선택 정렬(Selection Sort)
4
버블 정렬(Bubble Sort)
5
삽입 정렬(Insertion Sort)
해설
최악의 경우에도 비교 횟수가 인 알고리즘은 병합 정렬이다.
병합 정렬은 입력 상태와 무관하게 항상 절반씩 나누고 합치므로 최선·평균·최악 모두 이다.
- 퀵 정렬: 평균은 이지만 피벗이 한쪽으로 치우치면 최악 이다.
- 선택 정렬: 항상 번 비교한다.
- 버블 정렬: 최악 이다.
- 삽입 정렬: 역순 입력일 때 최악 이다.
오류나 개정된 내용이 보이면 알려주세요