Quick Sort
-
알고리즘, Sort, Quick SortData Structure & Algorithm 2024. 6. 18. 17:47
퀵 정렬(Quick Sort)은 Divide and Conquer 기법을 사용하는 매우 효율적인 정렬 알고리즘입니다. 평균적으로 매우 빠른 시간 복잡도인 O(n log n)을 가지며, 제자리 정렬(In-place Sort) 알고리즘입니다. 퀵 정렬은 리스트에서 피벗(pivot) 요소를 선택하고, 이를 기준으로 리스트를 두 개의 하위 리스트로 나누는 과정을 반복하여 정렬합니다.기본 개념퀵 정렬의 기본 개념은 다음과 같습니다:피벗 선택: 리스트에서 피벗 요소를 선택합니다.분할: 피벗을 기준으로 리스트를 두 개의 하위 리스트로 분할합니다. 피벗보다 작은 요소들은 피벗의 왼쪽으로, 피벗보다 큰 요소들은 피벗의 오른쪽으로 이동합니다.재귀 호출: 분할된 하위 리스트에 대해 퀵 정렬을 재귀적으로 호출합니다.결합: 하..