전설의 레전드1 [알고리즘] ep1-6) 퀵정렬(quick sort) ㅇ퀵정렬(quick sort): 분할통치법에 기초한 정렬 알고리즘"제자리 + unstable" O(nlog(n))※ 최악의 시간 복잡도: O(n^2) (이미 정렬된 리스트에서 항상 최악의 피벗을 선택하는 경우) 이름에서 알 수 있듯이 복잡하지만 매우 효율적인 알고리즘이다 일각에서는 이렇게 지칭한다 '살아있는 레전드' *피벗(pivot): 기준점1. 피벗을 기준점으로 잡는다2. 피벗보다 작으면 왼쪽에, 피벗보다 크면 오른쪽에 둔다3. 왼쪽과 오른쪽을 각각 정복한다 [분할 함수(partition 함수) 과정] 다양한 피봇 선정 방식 -> 다양한 퀵소트 버전 (참고)퀵정렬 트리: quickSort의 실행을 이진트리로 보이기이진트리의 각 노드는 quickSort의 재귀호출을 표현하며 다음을 저장- 실행.. 2024. 7. 7. 이전 1 다음
