Quick Sort Algorithm in Python

Quick Sort in Python

Sorting is a fundamental task in software engineering, and there exists a variety of algorithms that can be employed to arrange a list of elements. Among the most efficient sorting algorithms is Quicksort, which operates on the divide-and-conquer principle. Quicksort typically exhibits an average time complexity of O(n log n) and is widely used in practical applications.

This article will explore the Quicksort algorithm using Python, focusing on its implementation, performance metrics, and various optimization strategies.

How does the Quicksort Works in Python?

The Quicksort algorithm functions by dividing an array into two sub-arrays: one with elements that are less than a selected pivot element, and the other with elements that are greater than or equal to the pivot element. The pivot is chosen in a way that ensures it occupies its final position in the sorted array once the partitioning is complete.

The algorithm subsequently sorts the sub-arrays recursively by employing a comparable cycle for each sub-array. The recursive process halts when a sub-array contains fewer than two elements.

Example:

To illustrate the functioning of Quicksort in Python, let us consider an example.

Example


def quicksort(arr):

    if len(arr) < 2:

        return arr

    pivot = arr[0]

    left = [x for x in arr[1:] if x < pivot]

    right = [x for x in arr[1:] if x >= pivot]

    return quicksort(left) + [pivot] + quicksort(right)

The quicksort algorithm accepts an array named arr as its input and produces a sorted version of that array. The base case occurs when the length of arr is less than two, indicating that arr is already in a sorted state.

The pivot is selected as the initial element of the array. Subsequently, the sub-arrays are formed by dividing the elements that are lesser than the pivot into the left sub-array, while the elements that are greater than or equal to the pivot are placed into the right sub-array.

The sorted sub-arrays are obtained by invoking quicksort recursively on both the left and right segments. These sorted arrays are then combined with the pivot element to form the final sorted array.

Choosing the Pivot Element

The selection of the pivot element can significantly influence the efficiency of the Quicksort algorithm. If the pivot is chosen poorly, the algorithm may exhibit poor performance, and in certain scenarios, it could even demonstrate worst-case behavior with a time complexity of O(n^2).

A common method for selecting the pivot element involves taking the median of the first, middle, and last elements within the array. This strategy generally performs well in practice and can help avoid worst-case scenarios.

Partitioning the Array

The partitioning phase in Quicksort is critical for the algorithm's efficiency. In the implementation provided, list comprehensions are utilized to divide the array, which may lead to inefficiencies when dealing with large arrays.

A straightforward method for handling partitioning involves employing two indices to navigate the array from both ends, swapping elements that belong to the incorrect sub-array. This technique can enhance efficiency for large arrays and is frequently applied in practice.

Recursion in Quicksort

The recursive nature of the Quicksort algorithm can lead to stack overflow issues when dealing with very large arrays. To mitigate this risk, one can adopt a tail-recursive version of the algorithm, which enhances recursion by reusing the stack frame for the recursive invocation. However, since Python does not inherently optimize tail recursion, this approach may not result in significant performance improvements within Python.

Algorithm Implementation

Inputs:

A: an array of n elements

lo: the position of the initial element within the sub-array that requires sorting

hello: the position of the final element within the sub-array that requires sorting

Quicksort Algorithm:

✅ If lo is less than hi, then do the following: Call partition(A, lo, hi) and store the index of the pivot element in p. Recursively call quicksort(A, lo, p-1). Recursively call quicksort(A, p+1, hi).
✅ Call partition(A, lo, hi) and store the index of the pivot element in p.
✅ Recursively call quicksort(A, lo, p-1).
✅ Recursively call quicksort(A, p+1, hi).

Partition Algorithm:

✅ Let pivot be the last element of the sub-array A[lo..hi].
✅ Let i be the index of the first element of the sub-array.
✅ For each j from lo to hi-1, do the following: If A[j] <= pivot, then do the following: Increment i. Swap A[i] with A[j].
✅ Swap A[i+1] with A[hi].
✅ Return i+1.
✅ If A[j] <= pivot, then do the following: Increment i. Swap A[i] with A[j].
✅ Increment i.
✅ Swap A[i] with A[j].

Program Implementation for Quicksort in Python

Let us consider an example to illustrate the implementation of Quicksort in Python.

Example


# Python program for Quicksort

def quicksort(arr, lo, hi):

    """

    Sorts the given array in ascending order using the Quicksort algorithm.

    Parameters:

    arr (list): The array to be sorted

    lo (int): The index of the first element in the sub-array to be sorted

    hi (int): The index of the last element in the sub-array to be sorted

    """

    if lo < hi:

        # Partition the array and get the index of the pivot element

        p = partition(arr, lo, hi)

        # Recursively sort the left and right partitions

        quicksort(arr, lo, p-1)

        quicksort(arr, p+1, hi)

def partition(arr, lo, hi):

    """

    Partitions the sub-array by selecting the last element as the pivot,

    and rearranging the array so that all elements to the left of the pivot

    are less than or equal to the pivot, and all elements to the right of the

    pivot are greater than the pivot.

    Parameters:

    arr (list): The array to be partitioned

    lo (int): The index of the first element in the sub-array to be partitioned

    hi (int): The index of the last element in the sub-array to be partitioned

    Returns:

    int: The index of the pivot element after partitioning

    """

    # Select the last element as the pivot

    pivot = arr[hi]

    i = lo - 1

    # Loop through the sub-array and partition it

    for j in range(lo, hi):

        if arr[j] <= pivot:

            # Move the element to the left partition

            i += 1

            arr[i], arr[j] = arr[j], arr[i]

    # Move the pivot element to its final position in the array

    arr[i+1], arr[hi] = arr[hi], arr[i+1]

    # Return the index of the pivot element

    return i+1

# Example usage

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

n = len(arr)

quicksort(arr, 0, n-1)

print("Sorted array:", arr)

Output:

Output


Sorted array: [1, 5, 7, 8, 9, 10]

Time and Space Complexity of Quicksort

Time Complexity:

Quicksort has an average time complexity of O(n log n), with n representing the count of elements in the array. However, in the worst-case scenario, the time complexity reaches O(n^2). This situation arises when the chosen pivot is either the smallest or largest element in the array, resulting in sub-arrays that are poorly balanced.

Space complexity:

The average space complexity of the Quicksort algorithm is O(log n), attributed to its recursive nature. However, in the worst-case scenario, the space complexity can reach O(n), which occurs when the recursive calls are poorly balanced, resulting in an extended sequence of stack frames.

Comparing Quicksort to Other Sorting Algorithms

Quicksort is frequently regarded as one of the most efficient sorting algorithms, boasting an average time complexity of O(n log n) along with favorable memory usage. However, it can exhibit poor performance in the worst-case scenario, with a time complexity of O(n^2), making it less suitable for small datasets or data that is already nearly sorted. Other widely recognized sorting algorithms include Merge Sort, Heap Sort, and Insertion Sort. While Merge Sort maintains a worst-case time complexity of O(n log n), it necessitates additional memory for the purpose of merging the sub-arrays.

Heap Sort exhibits a worst-case time complexity of O(n log n) and does not require extra memory, although it may not be as memory-efficient as Quicksort. Insertion Sort, while having a time complexity of O(n^2), proves to be exceptionally efficient for small arrays and partially sorted datasets. The selection of a sorting algorithm depends on the particular application, the dimensions and arrangement of the data, as well as the resources at hand.

Quicksort Optimization Techniques

There are a few techniques that can be utilized to optimize the Quicksort algorithm and work on its performance. A portion of these techniques include:

✅ Randomized pivot selection: Rather than choosing the first element as the pivot, select a random element from the array. This can diminish the probability of worst-case conduct and work on the average performance of the algorithm.
✅ Tail recursion: Utilize a tail-recursive implementation of Quicksort to optimize the recursion and keep away from stack overflow errors.
✅ Hybrid algorithms: Utilize a hybrid algorithm calculation that joins Quicksort with one more sorting algorithm for little arrays or profoundly structured data. For example, use Insertion Sort for sub-arrays with under 10 elements.

Conclusion

Quicksort is an efficient sorting algorithm capable of sorting large arrays with an average time complexity of O(n log n). However, it can exhibit worst-case behavior with a time complexity of O(n^2) and may not be the best choice for small arrays or data that is heavily structured.