-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
퀵정렬
21.07.14 15:58 작성 조회수 86
0
안녕하세요! 강의 정말 잘 듣고 있습니다!
그런데 퀵정렬 마지막 부분에 조금 이해가 안되는 부분이 있어서 질문드립니다.
pivot을 low로 했을때, 잘 정렬된 리스트 일수록 퀵 정렬의 성능이 나빠진다고 하셨는데,
코드를 보면 잘 정렬된 리스트라도 무작위로 정렬된 리스트와 길이가 같다면 단위 연산의 실행횟수는 똑같을것으로 보이는데 왜 성능이 나빠진다고 하는지 궁금합니다.
잘 정렬된 리스트에 수행하지 않아도될 정렬 알고리즘이 수행되어서 비효율적으로 보여서 성능이 나빠졌다고 표현하신건지 궁금합니다!
답변을 작성해보세요.
0
주니온
지식공유자2021.07.14
정렬된 리스트를 가지고 시뮬레이션 해보면 쉽게 이해가 되실 겁니다.
S = [ 1, 2, 3, 4, 5]
위의 리스트를 파티션 하면, [1] 과 [2, 3, 4, 5]로 쪼개지지요?
S' = [ 2, 3, 4, 5] 도 마찬가지로
[2] , [3, 4, 5]로 쪼개집니다.
이런 식으로 재귀 호출의 깊이가 N이 되므로, Divide-and-Conquer의 장점이 사라지는 것이죠.
동일한 입력으로 Merge Sort를 하면 어떻게 될까요?
재귀 호출을 할 때 마다 N/2으로 쪼개어 지므로, 재귀 호출의 깊이가 logN이 됩니다.
답변 1