본문으로 건너뛰기
실습하기

퀵 정렬 파이썬으로 구현하기

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)

시간 복잡도​

  1. 최악의 경우 시간 복잡도 (Worst-Case Time Complexity): O(n^2)

    • 피벗 선택이 최악의 경우(예: 항상 최소값 또는 최대값을 피벗으로 선택)일 때 발생합니다. 이 경우, 배열이 하나의 요소로 분할되지 않고 계속해서 한 쪽으로 치우쳐지게 됩니다.

  2. 최선의 경우 시간 복잡도 (Best-Case Time Complexity): O(nlog n)

    • 이는 피벗이 매번 배열의 중간 값을 분할하는 경우에 해당합니다. 각 분할은 배열을 절반으로 줄여, 로그 시간 복잡도를 갖게 됩니다.

  3. 평균 시간 복잡도 (Average-Case Time Complexity): O(nlog n)

    • 대부분의 경우, 퀵 정렬은 평균적으로 nlog n의 시간 복잡도를 가집니다. 이는 피벗 선택이 균등하게 이루어질 때의 기대 시간 복잡도입니다.

다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!