Quick Sort는 왜 Quick Sort 일까요?

[jjangsungwon]

Quick Sort는 최악의 경우 n^2의 시간 복잡도를 가지는데 왜 일반적으로 가장 빠른 정렬 알고리즘을 Quick Sort라고 할까요?

저는 두 가지 장점 때문에 일반적으로 Quick Sort가 가장 빠른 정렬 알고리즘이라고 생각합니다.
첫째, In-place입니다. 시간 복잡도뿐만 아니라 공간 복잡도도 중요한 속성이라고 생각합니다.
둘째, 비교 대상이 pivot뿐입니다. 따라서 pivot을 캐시 메모리처럼 빠르게 접근할 수 있는 메모리와 접목시키면 시간 효율을 높일 수 있다고 생각합니다.

혹시 다른 이유가 있을까요?

[cheonjiwan]

좋은 질문 감사합니다.
Quick Sort가 가장 빠른 정렬 알고리즘이라고 불리는 이유는 말씀하신 두가지 장점 이외에도
개인적인 생각이지만 pivot을 어떻게 설정하느냐에 따라 알고리즘을 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하기 때문도 있지 않을까 생각합니다.

[jjangsungwon]

좋은 답변 감사합니다!
하지만 pivot을 어떻게 설정하느냐에 따라 알고리즘을 제곱 시간보다 적게 설계할 수 있는지는 pivot을 정하고 수행한 결과를 봐야지만 알 수 있지않을까요?

[cheonjiwan]

넵 그렇긴 하지만 그런 설계를 가능하다는 점이 장점이 아닐까 싶습니다..

[jjangsungwon]

다른 정렬 알고리즘에 비해서 그런 설계가 가능하다는 점도 큰 장점인 것 같네요👍 답변 너무 감사드립니다!!

[ChanhuiSeok]

이와 관련된 주제로 좋은 글들을 발견해서 주소를 남겨 봅니다!
https://brunch.co.kr/@k2u4yt/3
https://velog.io/@agugu95/%EC%B0%B8%EC%A1%B0%EC%9D%98-%EC%A7%80%EC%97%AD%EC%84%B1%EA%B3%BC-Quicksort-vs-Mergesort

[jjangsungwon]

좋은 글 공유해주셔서 감사드립니다😊