Implementing Quick Sort in Python

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.

Copy
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]

Recursively sort the left and right sub-arrays.

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

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.