상상면접 : 퀵정렬 (정렬)

면접관 : 알고 있는 정렬 알고리즘을 하나 설명해주세요.

 

나 : 퀵정렬에 대해서 설명하겠습니다.

 

나 : 우선 퀵정렬은 분할 정복 알고리즘으로 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략입니다. 퀵정렬은 분할, 정복, 결합의 단계들로 이루어집니다.

 

나 : 과정을 설명하겠습니다.

먼저 배열안의 한 요소를 피벗으로 설정합니다.

피벗을 기준으로 피벗보다 작은요소는 피벗의 왼쪽으로 피벗보다 큰 요소는 피벗의 오른쪽으로 옮깁니다.

피벗을 제외한 왼쪽 배열과 오른쪽 배열을 다시 정렬 합니다.

분할된 부분 배열에서 다시 피벗을 정한 후 피벗을 기준으로 2개의  부분배열로 나누는 과정을 반복합니다.

이런 과정을 부분 배열들이 더 이상 분할할 수 없을 때 까지 반복하고 다시 원래의 정렬에 합병게 되면 정렬이 완료됩니다.

 

면접관 : 퀵소트의 장점과 단점이 뭐라고 생각하나요?

 

나 : 장점은 이름 그대로 속도가 빠르다는 점입니다. 시간복잡도는 O(nlogn)이며 다른 정렬 알고리즘과 비교했을 때 가장 빠릅니다. 그리고, 추가적인 메모리 공간을 필요로 하지 않습니다.

하지만 단점은 정렬된 배열에 대해서는 오히려 수행시간이 더 걸리게 됩니다.

 

면접관 : 왜 정렬된 배열에 대해서 수행시간이 더 길어지나요?

 

나 : 예를 들어 피봇을 가장 앞에 위치하는 원소로 잡는다면 분할 과정에서 피봇값보다 작은 값은 없기에 비대칭 적인 파티션으로 나누어지게 됩니다. 이런 방식으로 피봇을 계속 설정하면 분할이 일어날 때마다 비대칭적인 파티션으로 나뉘기 때문에 시간복잡도가 O(n^2)이 되기 때문에 수행시간이 일반적인 경우보다 훨씬 길어지게 됩니다.

 

면접관 : 이런 최악의 경우를 막으려면 어떻게 해야할까요?

 

나 : 난수를 발생시켜 피벗을 랜덤하게 뽑는 경우를 생각해볼 수 있습니다. 이렇게 하면 적어도 정렬된 배열에 대해서 위의 예시에서 든 방법처럼 오랜 시간이 걸리지는 않을 것입니다.