← Back to Data Structures and Algorithms in Python

1. Introduction

Quick Sort is an efficient, in-place, comparison-based sorting algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

2. Implementation Steps

1. Choose a 'pivot' element from the array and partition the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.

2. Recursively apply the above steps to the sub-arrays.

3. Combine the sub-arrays and the pivot to get a sorted array.

3. Implementation in Python

def quick_sort(arr):
    # Base condition
    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)
arr = [3, 6, 8, 10, 1, 2, 1]
print(quick_sort(arr))

Output:

[1, 1, 2, 3, 6, 8, 10]

Explanation:

1. The function quick_sort begins by checking the length of the input array, arr. If its length is less than or equal to 1, it is already sorted, and we return it directly.

2. A pivot element is chosen from the array, in this case, it's the middle element.

3. Using list comprehensions, the array is split into three parts:

- left: contains elements less than the pivot

- middle: contains elements equal to the pivot

- right: contains elements greater than the pivot

4. The function then recursively sorts the left and right sub-arrays.

5. Finally, the sorted array is obtained by concatenating the sorted left array, middle, and the sorted right array.

This approach divides the problem into smaller problems (sub-arrays) and then combines the solutions of the sub-problems to get the solution to the original problem. The average time complexity of the Quick Sort algorithm is O(n log n), but in the worst case, it can go up to O(n^2).