StrangeDeveloper StrangeDeveloper

일반적으로 퀵정렬은 평균적으로 O(n log n)이라는 시간복잡도를 갖습니다. 하지만 최악의 경우에는 O(n²)이라는 시간복잡도를 갖게되지요. 개발자들은 퀵정렬의 평균적이라는 장점을 살리고 최악의 경우를 보완하는 알고리즘을 만들고자 했습니다. 즉, 최악의 경우에도 O(n log n)을 만족하고자 하는 것인데요, 결국, 개발자들은 퀵정렬이 최악의 경우에도 시간복잡도가 O(n log n)이 되는 방법을 찾았습니다. 아이디어는 간단합니다. 퀵정렬을 사용하되 다른 알고리즘들과 혼합하여 사용하면 됩니다. 다만 특이한 점은 1차 임계값과 2차 임계값이 존재하여 각 알고리즘 사용 구간을 구분해준다는 점입니다. 맨 처음 정렬에는 퀵소트를 사용합니다. 그리고 재귀적으로 퀵소트를 사용하면서 분할되는 횟수를 스스로 모니터링..