Quick sort의 경우 평균적으로 O(nlogn)의 시간 복잡도를 가지며, 대부분의 경우 효율적인 성능을 보인다.
또 Quick Sort는 다른 정렬 알고리즘과 달리 추가적인 메모리 공간을 필요로 하지 않는 in-place sorting 알고리즘이기 때문에, 메모리를 효율적으로 사용할 수 있다.
또한 Quick sort는 알고리즘의 구현이 간단하며, 기본적으로 많은 언어들의 표준 정렬 함수로 구현되어 있다.
따라서 대부분의 경우 Quick sort를 사용하면 높은 성능과 구현의 용이성을 동시에 얻을 수 있기 때문에 가장 많이 사용되는 알고리즘이다.
다만 최악의 경우 시간 복잡도가 O(n^2)까지 증가할 수 있다.
이러한 경우를 방지하기 위해서, pivot값을 선택하는 방법을 최적화하는 등의 방법이 사용될 수 있다.
좀 더 나아가서 Quick sort의 핵심을 알아보자
핵심은 분할 정복이다.
quick sort의 과정은 다음과 같다.
분할(Divide):배열을 pivot 값 기준으로 두 개의 부분 배열로 나눕니다.
정복(conquer):부분 배열을 정렬합니다.
합병(merge):부분 배열을 합쳐서 정렬된 배열을 만든다.
이러한 과정을 이해한다면 quick sort의 장점을 알 수 있다.
cf)in-place sorting(제자리 배열)의 가장 큰 장점은 추가적인 메모리 공간을 필요로 하지 않는다는 점이다.
이를 통해서 메모리 사용을 최적화할 수 있고, 메모리 제한이 있는 환경에서도 사용할 수 있다.
또 정렬된 결과를 복사하거나 이동하는 데 드는 시간과 비용을 줄일 수도 있다.
또한 더 빠른 실행 속도와 더 나은 캐시 지역성을 제공한다. 추가 메모리 할당 없이 원래 배열에서 작업하기 때무에, cpu캐시 메모리의 지역성을 높일 수 있다.
한 줄 요약 : 메모리 제한이나 실행 속도를 고려할 때 유용한 방법이다.
