이론도 좋지만 작업속도를 위해서는 라이브러리 이용하는게 좋다.
최악의 경우 O(n^2)인 삽입 정렬은 작은 배열에 대해서는 낮은 오버헤드 때문에 종종 더 빠릅니다. 작은 입력 크기로 인해 상수 인수와 하위 항이 더 중요해집니다.
계수 정렬은 숫자의 범위 (즉, 최대와 최소 간의 차이)가 정렬할 값의 수보다 크게 늘어나지 않을 때 가장 잘 작동합니다. int의 경우 범위는 -2147483648에서 2147483647까지로, 발생 횟수를 계산하기 위해 매우 큰 보조 배열이 필요하기 때문에 대부분의 시나리오에서 효과적으로 처리할 수 없습니다.
이러한 타입의 범위는 훨씬 작습니다. 예를 들면:
byte: -128에서 127까지 char: 0에서 65535까지 (Java에서 char는 부호 없음) short: -32768에서 32767까지 이러한 작은 범위로 인해 계수 정렬은 보조 계수 배열이 과도하게 크지 않기 때문에 매우 효과적일 수 있습니다.
퀵 정렬은 좋은 평균 시간 복잡도인 O(n log n)을 가진 분할 정복 알고리즘입니다. 듀얼 피벗 퀵 정렬은 두 개의 피벗을 사용하는 전통적인 퀵 정렬의 약간 최적화된 버전입니다.
언급했듯이, 계수 정렬의 효율성은 공간에 대한 비용으로 옵니다. 길이가 10인 short 배열의 경우 값의 구별되는 수는 최대 10까지입니다. 그러나 범위는 훨씬 큽니다(0에서 65535까지). 계수 정렬을 사용하면, 실제 데이터가 10개의 값으로만 구성되어 있더라도 short가 가질 수 있는 모든 가능한 값에 대해 계정할 수 있는 크기 65536의 보조 배열이 필요합니다. 이는 작은 데이터 세트에 대해 비효율적입니다.
이것은 공간 복잡성에 관한 포인트를 제시하는 것 같습니다. 계수 정렬은 평균 O(n) 시간 복잡도의 장점을 가져올 수 있지만, 큰 보조 계수 배열을 생성하고 초기화하는 오버헤드는 계수 정렬의 시간적 이점을 상쇄할 수 있습니다.