Quick Sort (Python)

[qingquan-li]

def partition(arr, start, end):
    # Choose the last element as the pivot
    pivot = arr[end]
    # Index for the smaller element
    partition_index = start - 1

    for current_index in range(start, end):
        if arr[current_index] <= pivot:
            partition_index += 1
            # Swap the elements at partition_index and current_index
            arr[partition_index], arr[current_index] = arr[current_index], arr[partition_index]

    # Place the pivot element in its correct position
    arr[partition_index + 1], arr[end] = arr[end], arr[partition_index + 1]

    return partition_index + 1


def quick_sort(arr, start, end):
    if start < end:
        # Partition the array and get the partitioning index
        pivot_index = partition(arr, start, end)

        # Recursively sort elements before and after the partition
        quick_sort(arr, start, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, end)


A = [5, 6, 7, 2, 1, 4]
quick_sort(A, 0, len(A) - 1)
print("Sorted array:", A)  # Sorted array: [1, 2, 4, 5, 6, 7]