Quick Sort in Python

Quick sort is a fast, efficient sorting algorithm that uses the divide-and-conquer approach. It works by selecting a pivot element from the list and partitioning the other elements into two sublists based on whether they are less than or greater than the pivot. The sublists are then recursively sorted, and the final sorted list is obtained by combining the sorted sublists.

Here is an implementation of quick sort in Python:

def quick_sort(lst):
    # Base case: if the list has fewer than two elements, it is already sorted
    if len(lst) < 2:
        return lst
    
    # Select the pivot element and partition the list around it
    pivot = lst[0]
    less = [x for x in lst[1:] if x <= pivot]
    greater = [x for x in lst[1:] if x > pivot]
    
    # Recursively sort the sublists
    less_sorted = quick_sort(less)
    greater_sorted = quick_sort(greater)
    
    # Combine the sorted sublists and return the result
    return less_sorted + [pivot] + greater_sorted

# Test the quick sort function
lst = [5, 4, 3, 2, 1]
print(quick_sort(lst))  # Output: [1, 2, 3, 4, 5]

Using Recursion:

def quick_sort_recursive(lst):
    # Base case: if the list has fewer than two elements, it is already sorted
    if len(lst) < 2:
        return lst
    
    # Select the pivot element and partition the list around it
    pivot = lst[0]
    less = [x for x in lst[1:] if x <= pivot]
    greater = [x for x in lst[1:] if x > pivot]
    
    # Recursively sort the sublists
    less_sorted = quick_sort_recursive(less)
    greater_sorted = quick_sort_recursive(greater)
    
    # Combine the sorted sublists and return the result
    return less_sorted + [pivot] + greater_sorted

# Test the quick sort function
lst = [5, 4, 3, 2, 1]
print(quick_sort_recursive(lst))  # Output: [1, 2, 3, 4, 5]

This implementation of quick sort works in the same way as the iterative version, but it uses recursion to sort the sublists instead of using a loop. The base case for the recursion is when the list has fewer than two elements, in which case the list is already sorted.

Quick sort has a time complexity of O(n log n) in the average case and O(n^2) in the worst case. However, it is generally faster than other O(n log n) sorting algorithms such as merge sort because it has a smaller constant factor. It is also an in-place sorting algorithm, which means that it does not require additional memory to store the sorted list.