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 array:', sorted_list)

# Implementing Quick Sort in Python

## 1. Pivot Selection and Partition

Select a pivot from the array and partition the array into two parts based on the pivot.

During this process, all elements smaller than the pivot are placed to the left, and elements larger are placed to the right.

```python title="Pivot Selection and Partition"
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. Recursive Sorting

Recursively sort the left and right sub-arrays.

```python title="Example of Recursive Sorting"
return quick_sort(left) + middle + quick_sort(right)
```

<br />

## Time Complexity

1. `Worst-Case Time Complexity`: O(n^2)

   - Occurs when pivot selection is unfortunate (e.g., always choosing the minimum or maximum value as the pivot). In this case, the array does not divide evenly and continues to be skewed to one side.

2. `Best-Case Time Complexity`: O(nlog n)

   - Applicable when the pivot consistently divides the array into two equal halves. Each division reduces the array size by half, resulting in logarithmic time complexity.

3. `Average-Case Time Complexity`: O(nlog n)

   - In most situations, Quick Sort has an average time complexity of nlog n, assuming that pivot selection is uniformly balanced.