입력값의 범위에 따른 Quick sort의 성능차이
알고리즘을 풀때 입력값의 범위를 크게 주어 Arrays.sort()를 사용했을때 run tume error가 발생하게끔 만들어 사용하지 못하게 만든 문제가 있었습니다.
결과부터 말 하자면, 퀵소트를 사용할 때 입력 값의 범위가 크면 성능이 저하되기 때문입니다.
왜 Arrays.sort()를 사용할 때 입력값의 범위에 따라 성능 차이가 발생할까요 ?
바로 dual-pivot Quicksort알고리즘을 사용하기 때문입니다.
Dual-pivot Quicksort는 기존의 Quicksort가 하나의 피벗을 사용하여 배열을 두 개의 부분으로 나누는 것과 달리, 두 개의 피벗을 사용하여 배열을 세 개의 부분으로 나눕니다.
- 첫 번째 피벗(pivot1)보다 작은 값
- 두 번째 피벗(pivot2)보다 큰 값
- 두 피벗 사이의 값
퀵소트의 성능은 피벗을 어떻게 선택하느냐에 따라 성능이 크게 달라집니다.
만약, 배열이 이미 정렬되어있어 항상 피벗으로 첫번째나 마지막 요소를 선택하게 된다면 어떻게 될까요 ?
배열이 계속해서 한쪽으로 치우치게 되므로, 퀵소트는 n-1개의 원소를 가진 하위배열로 나누어 지기 때문에 시간복잡도로 worst case인 의 시간복잡도를 가집니다.
입력값의 범위는 피벗을 얼마나 잘 선택하는지에 영향을 미칩니다.
만약 배열이 다음과 같이 입력값의 범위가 넓고 값들이 고르게 분포되어있지 않은 경우, 피벗을 선택할때 배열을 균등하게 나누지 못하고 한쪽으로 치우치게 되어 성능이 저하될 수 있습니다.
피벗을 선택하는 경우에는 배열의 중간값을 선택하고 나머지 피벗은 배열의 끝값을 선택합니다.
만약, 값의 범위가 좁다고 해봅시다.
이 경우, 중간값과 끝값을 피벗으로 선택하면 배열은 균등하게 나누어집니다.
값의 범위가 넓은 경우를 살펴봅시다.
이 경우, 중간 인덱스의 값은 1이고 끝값은 99999999입니다.
피벗을 중간값과 끝값으로 선택하면:
- 중간값 1을 기준으로 나누면, 대부분의 값이 1로 나뉘고, 오른쪽에 극단적인 값 99999999만 남습니다.
- 끝값 99999999를 기준으로 나누면, 99999999보다 작은 모든 값이 한쪽에 몰리게 됩니다.
이렇게 되면, 배열이 균등하게 나누어지지 않고 대부분의 값이 한쪽에 몰리게 되어, 퀵소트의 성능이 으로 떨어집니다.
따라서, 값들이 고르게 분포되지 않으면 비효율적인 분할이 발생할 수 있습니다.
