가이드라인
실습
퀵 정렬 파이썬으로 구현하기
1. 피벗 선택 및 분할
배열에서 피벗을 선택하고, 피벗을 기준으로 배열을 두 부분으로 나눕니다.
이 과정에서 모든 요소는 피벗보다 작은 값은 피벗의 왼쪽에, 큰 값은 오른쪽에 위치하게 됩니다.
피벗 선택 및 분할
pivot = arr[len(arr) // 2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot]
2. 재귀적 정렬
왼쪽 및 오른쪽 서브 배열을 재귀적으로 정렬합니다.
재귀적 정렬 예시
return quick_sort(left) + middle + quick_sort(right)
시간 복잡도
-
최악의 경우 시간 복잡도 (Worst-Case Time Complexity)
: O(n^2)- 피벗 선택이 최악의 경우(예: 항상 최소값 또는 최대값을 피벗으로 선택)일 때 발생합니다. 이 경우, 배열이 하나의 요소로 분할되지 않고 계속해서 한 쪽으로 치우쳐지게 됩니다.
-
최선의 경우 시간 복잡도 (Best-Case Time Complexity)
: O(nlog n)- 이는 피벗이 매번 배열의 중간 값을 분할하는 경우에 해당합니다. 각 분할은 배열을 절반으로 줄여, 로그 시간 복잡도를 갖게 됩니다.
-
평균 시간 복잡도 (Average-Case Time Complexity)
: O(nlog n)- 대부분의 경우, 퀵 정렬은 평균적으로 nlog n의 시간 복잡도를 가집니다. 이는 피벗 선택이 균등하게 이루어질 때의 기대 시간 복잡도입니다.
가이드라인
AI 튜터
배포
디자인
업로드
수업 노트
즐겨찾기
도움말