36.분할 정복(Divide and Conquer)에 기반한 알고리즘으로 피벗(pivot)을 사용하며 최악의 경우 회의 비교를 수행해야 하는 정렬(Sort)은?

해설

- Selection Sort - 배열 내에서 최소값을 찾은 다음 정렬 되지 않은 맨 앞 값과 교환을 하며 정렬을 해 나아가는 방법 (정렬 시간 복잡도 모두 O(n^2)) - Bubble Sort - 왼쪽에서 부터 두 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터 보다 크면 자리를 바꾸는 정렬 알고리즘(정렬 시간 복잡도 모두 O(n^2)) - Insert Sort - 한 개의 값을 추출한 다음 앞쪽으로 비교해서 본인의 자리를 알맞게 찾아가게끔 하는 정렬 방법. 정렬 시간 복잡도는 최상일 경우 O(n), 평균과 최악일 경우 O(n^2) - 병합 정렬 - 또한 분할 정복에 기반한 알고리즘으로 리스트를 1 이하인 상태까지 절반으로 자른 다음 재귀적으로 합병 정렬을 이용해서 전체적인 리스트를 합병하는 정렬 과정. O(n log n) ※ n(n-1)/2 = O(n^2)