Quick Sort with a List

def quick_sort(arr):
    # Base case: if the list is empty or has one element, it is already sorted
    if len(arr) <= 1:
        return arr
    else:
        # Select the pivot element (here, we choose the middle element)
        pivot = arr[len(arr) // 2]
        
        # Partition the list into three parts: less than, equal to, and greater than the pivot
        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 apply quick_sort to the left and right partitions, and concatenate the results
        return quick_sort(left) + middle + quick_sort(right)

# Example usage:
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("Sorted array:", sorted_arr)

Step 1: Base Case: If the list has zero or one element, it is already sorted, so we return it as is.

Step 2: Choosing a Pivot: We choose the middle element of the list as the pivot.

Step 3: Partitioning:

• Left: All elements less than the pivot.
• Middle: All elements equal to the pivot.
• Right: All elements greater than the pivot.

Step 4: Recursion: Recursively apply the quick_sort function to the left and right sublists.

Step 5: Concatenation: Combine the sorted left sublist, middle list, and sorted right sublist to get the final sorted list.

more efficient ways to choose a pivot and partition the list

• improves performance by choosing a better pivot and performing partitioning in-place, which reduces the overall space complexity.

def median_of_three(arr, low, high):
    mid = (low + high) // 2
    # Sorting the first, middle, and last elements to find the median
    if arr[low] > arr[mid]:
        arr[low], arr[mid] = arr[mid], arr[low]
    if arr[low] > arr[high]:
        arr[low], arr[high] = arr[high], arr[low]
    if arr[mid] > arr[high]:
        arr[mid], arr[high] = arr[high], arr[mid]
    return arr[mid]

def partition(arr, low, high):
    pivot = median_of_three(arr, low, high)
    i = low - 1
    j = high + 1
    while True:
        # Increment i while arr[i] < pivot
        i += 1
        while arr[i] < pivot:
            i += 1
        # Decrement j while arr[j] > pivot
        j -= 1
        while arr[j] > pivot:
            j -= 1
        # If two pointers met
        if i >= j:
            return j
        # Swap elements at i and j
        arr[i], arr[j] = arr[j], arr[i]

def quick_sort(arr, low, high):
    if low < high:
        # Partition the array and get the pivot index
        pivot_index = partition(arr, low, high)
        # Recursively apply quick_sort to the left and right partitions
        quick_sort(arr, low, pivot_index)
        quick_sort(arr, pivot_index + 1, high)

# Example usage:
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr, 0, len(arr) - 1)
print("Sorted array:", arr)

Step 1: Median of Three: This function selects the median of the first, middle, and last elements of the array segment to use as the pivot. This helps to avoid worst-case scenarios like already sorted arrays.

Step 2: Partition Function:

• Pivot Selection: Uses the median of three to select the pivot.
• Pointer Movement: Two pointers, i and j, are used to scan the array from the left and right, respectively. They move towards each other until they find elements that are out of place relative to the pivot, then they swap these elements.
• Termination: The loop continues until the two pointers cross, at which point the function returns the index of the partition.

Step 3: Quick Sort Function: Recursive Calls: Applies Quick Sort recursively to the left and right segments of the array divided by the partition index.