lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

lesson13Title

lesson14Title

lesson15Title

lesson16Title

lesson17Title

pythonIntroAlgorithms2Chapter1Title

pythonIntroAlgorithms2Chapter2Title

pythonIntroAlgorithms2Chapter3Title

pythonIntroAlgorithms2Chapter4Title

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    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]

    return quick_sort(left) + middle + quick_sort(right)


example_list = [10, 7, 8, 9, 1, 5]

sorted_list = quick_sort(example_list)


print('정렬된 배열', sorted_list)

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

## 1. 피벗 선택 및 분할

배열에서 피벗을 선택하고, 피벗을 기준으로 배열을 두 부분으로 나눕니다.

이 과정에서 모든 요소는 피벗보다 작은 값은 피벗의 왼쪽에, 큰 값은 오른쪽에 위치하게 됩니다.

```python title="피벗 선택 및 분할"
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]
```

<br />

## 2. 재귀적 정렬

왼쪽 및 오른쪽 서브 배열을 재귀적으로 정렬합니다.

```python title="재귀적 정렬 예시"
return quick_sort(left) + middle + quick_sort(right)
```

<br />

## 시간 복잡도

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의 시간 복잡도를 가집니다. 이는 피벗 선택이 균등하게 이루어질 때의 기대 시간 복잡도입니다.