Quick Sort Implementation in Python

Quick sort is a popular sorting algorithm that uses a divide-and-conquer approach to sort elements in an array or list. 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 recursively sorted. In this article, we will explore how to implement the Quick sort algorithm in Python.

How Quick Sort Works

The Quick sort algorithm works as follows:

1. Choose a pivot element from the array. This can be any element, but it is common to choose the first or last element.
2. Partition the other elements into two sub-arrays, according to whether they are less than or greater than the pivot.
3. Recursively apply the above steps to the sub-arrays.

Implementing Quick Sort in Python

Now that we know how Quick sort works, let’s look at how we can implement it in Python.

First Implementation

Here is a simple implementation of Quick sort:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        left = []
        right = []
        for i in arr[1:]:
            if i < pivot:
                left.append(i)
            else:
                right.append(i)
        return quick_sort(left) + [pivot] + quick_sort(right)

Let’s walk through this implementation step-by-step:

1. First, we check if the length of the array is less than or equal to 1. If it is, we return the array since it is already sorted.
2. If the length of the array is greater than 1, we choose a pivot element. In this case, we choose the first element of the array.
3. We create two empty arrays, left and right.
4. We iterate over the remaining elements in the array, and for each element, we check if it is less than the pivot. If it is, we append it to the left array. If it is greater than or equal to the pivot, we append it to the right array.
5. We then recursively call the quick_sort function on the left and right sub-arrays, and concatenate the results with the pivot element in the middle.

Let’s test this implementation with an example:

arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = quick_sort(arr)
print(sorted_arr)

The output of this code will be:

[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

Time and Space Complexity

The time complexity of Quick sort is O(n log n) in the average case and O(n^2) in the worst case. The worst case occurs when the pivot element is always the smallest or largest element in the array, resulting in unbalanced partitions.

The space complexity of Quick sort is O(log n) in the average case and O(n) in the worst case. The worst case occurs when the recursion depth is equal to the size of the array.

Second Implementation

Here is another implementation of Quick sort that uses a different partitioning algorithm:

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1
def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
n = len(arr)
quick_sort(arr, 0, n - 1)
print(arr)

Let’s walk through this implementation step-by-step:

1. We define a partition function that takes an array, a low index, and a high index as arguments. The pivot element is chosen as the last element in the array.
2. We initialize i to be one less than the low index.
3. We iterate over the array from low to high, swapping elements that are less than or equal to the pivot with elements that are greater than the pivot. We increment i every time we swap elements.
4. We swap the pivot element with the element at i + 1.
5. We return the index of the pivot element.
6. We define a quick_sort function that takes an array, a low index, and a high index as arguments. If the low index is less than the high index, we partition the array and recursively call quick_sort on the left and right sub-arrays.
7. We call the quick_sort function on the entire array to sort it.

Let’s test this implementation with the same example:

arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
n = len(arr)
quick_sort(arr, 0, n - 1)
print(arr)

The output of this code will be:

[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

Conclusion

Quick sort is a popular sorting algorithm that is efficient and easy to implement. It works by partitioning an array around a pivot element and recursively sorting the left and right sub-arrays. The choice of pivot element can affect the performance of the algorithm, but there are ways to mitigate this issue. Quick sort has a time complexity of O(n log n) in the average case and O(n^2) in the worst case, and a space complexity of O(log n) in the average case and O(n) in the worst case. There are different partitioning algorithms that can be used in Quick sort, and the implementation we showed in this example uses a simple one that chooses the last element in the array as the pivot.