def partition(arr, low, high):
pivot = arr[high] # Choose the last element as the pivot
i = low - 1 # Index of the smaller element
for j in range(low, high):
# If the current element is smaller than or equal to the pivot
if arr[j] <= pivot:
i += 1 # Increment the index of the smaller element
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quickSort(arr, low, high):
if low < high:
# Partitioning index
pi = partition(arr, low, high)
# Recursively sort elements before and after partition
quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
if __name__ == "__main__":
arr = [12, 11, 13, 5, 6, 7]
print("Original Array:", arr)
quickSort(arr, 0, len(arr) - 1)
print("Sorted Array:", arr)