[알고리즘] 퀵 정렬 (Quick Sort)

목 차 퀵 정렬(Quick Sort) 기본 개념 퀵 정렬을 구현하며 배운 것들 구현 방법 퀵 정렬(Quick Sort) 기본 개념 퀵 정렬은 분할 정복 전략(Divide and Conquer)을 사용한다. 평균 O(n log n)의 시간 복잡도를 가지고, 최악의 경우(정렬된 배열) O(n^2)의 시간 복잡도를 가진다. pivot 을 먼저 선택하고 그 pivot을 기준으로 더 큰 값과 더 작은 값을 분류한다. 이 것을 '파티셔닝'이라고 하며, 재귀적으로 정렬을 한다. pivot 의 중요성 퀵 정렬에서 pivot 은 시간 복잡도에 큰 영향을 끼친다. 일반적으로 첫 번째 인덱스, 중간 인덱스, 마지막 인덱스를 pivot 으로 설정한다. 퀵 정렬을 구현하며 배운 것들 내가 알고 있던 개념들을 사용하였기에 기술적..

Algorithm 2023.12.26