# Quick sort in Python
# function to find the partition position
def partition(array, low, high):
# choose the rightmost element as pivot
pivot = array[high]
# pointer for greater element
i = low - 1
# traverse through all elements
# compare each element with pivot
for j in range(low, high):
if array[j] <= pivot:
# if element smaller than pivot is found
# swap it with the greater element pointed by i
i = i + 1
# swapping element at i with element at j
(array[i], array[j]) = (array[j], array[i])
# swap the pivot element with the greater element specified by i
(array[i + 1], array[high]) = (array[high], array[i + 1])
# return the position from where partition is done
return i + 1
# function to perform quicksort
def quickSort(array, low, high):
if low < high:
# find pivot element such that
# element smaller than pivot are on the left
# element greater than pivot are on the right
pi = partition(array, low, high)
# recursive call on the left of pivot
quickSort(array, low, pi - 1)
# recursive call on the right of pivot
quickSort(array, pi + 1, high)
data = [8, 7, 2, 1, 0, 9, 6]
print("Unsorted Array")
print(data)
size = len(data)
quickSort(data, 0, size - 1)
print('Sorted Array in Ascending Order:')
print(data)
IyBRdWljayBzb3J0IGluIFB5dGhvbgoKIyBmdW5jdGlvbiB0byBmaW5kIHRoZSBwYXJ0aXRpb24gcG9zaXRpb24KZGVmIHBhcnRpdGlvbihhcnJheSwgbG93LCBoaWdoKToKCiAgIyBjaG9vc2UgdGhlIHJpZ2h0bW9zdCBlbGVtZW50IGFzIHBpdm90CiAgcGl2b3QgPSBhcnJheVtoaWdoXQoKICAjIHBvaW50ZXIgZm9yIGdyZWF0ZXIgZWxlbWVudAogIGkgPSBsb3cgLSAxCgogICMgdHJhdmVyc2UgdGhyb3VnaCBhbGwgZWxlbWVudHMKICAjIGNvbXBhcmUgZWFjaCBlbGVtZW50IHdpdGggcGl2b3QKICBmb3IgaiBpbiByYW5nZShsb3csIGhpZ2gpOgogICAgaWYgYXJyYXlbal0gPD0gcGl2b3Q6CiAgICAgICMgaWYgZWxlbWVudCBzbWFsbGVyIHRoYW4gcGl2b3QgaXMgZm91bmQKICAgICAgIyBzd2FwIGl0IHdpdGggdGhlIGdyZWF0ZXIgZWxlbWVudCBwb2ludGVkIGJ5IGkKICAgICAgaSA9IGkgKyAxCgogICAgICAjIHN3YXBwaW5nIGVsZW1lbnQgYXQgaSB3aXRoIGVsZW1lbnQgYXQgagogICAgICAoYXJyYXlbaV0sIGFycmF5W2pdKSA9IChhcnJheVtqXSwgYXJyYXlbaV0pCgogICMgc3dhcCB0aGUgcGl2b3QgZWxlbWVudCB3aXRoIHRoZSBncmVhdGVyIGVsZW1lbnQgc3BlY2lmaWVkIGJ5IGkKICAoYXJyYXlbaSArIDFdLCBhcnJheVtoaWdoXSkgPSAoYXJyYXlbaGlnaF0sIGFycmF5W2kgKyAxXSkKCiAgIyByZXR1cm4gdGhlIHBvc2l0aW9uIGZyb20gd2hlcmUgcGFydGl0aW9uIGlzIGRvbmUKICByZXR1cm4gaSArIDEKCiMgZnVuY3Rpb24gdG8gcGVyZm9ybSBxdWlja3NvcnQKZGVmIHF1aWNrU29ydChhcnJheSwgbG93LCBoaWdoKToKICBpZiBsb3cgPCBoaWdoOgoKICAgICMgZmluZCBwaXZvdCBlbGVtZW50IHN1Y2ggdGhhdAogICAgIyBlbGVtZW50IHNtYWxsZXIgdGhhbiBwaXZvdCBhcmUgb24gdGhlIGxlZnQKICAgICMgZWxlbWVudCBncmVhdGVyIHRoYW4gcGl2b3QgYXJlIG9uIHRoZSByaWdodAogICAgcGkgPSBwYXJ0aXRpb24oYXJyYXksIGxvdywgaGlnaCkKCiAgICAjIHJlY3Vyc2l2ZSBjYWxsIG9uIHRoZSBsZWZ0IG9mIHBpdm90CiAgICBxdWlja1NvcnQoYXJyYXksIGxvdywgcGkgLSAxKQoKICAgICMgcmVjdXJzaXZlIGNhbGwgb24gdGhlIHJpZ2h0IG9mIHBpdm90CiAgICBxdWlja1NvcnQoYXJyYXksIHBpICsgMSwgaGlnaCkKCgpkYXRhID0gWzgsIDcsIDIsIDEsIDAsIDksIDZdCnByaW50KCJVbnNvcnRlZCBBcnJheSIpCnByaW50KGRhdGEpCgpzaXplID0gbGVuKGRhdGEpCgpxdWlja1NvcnQoZGF0YSwgMCwgc2l6ZSAtIDEpCgpwcmludCgnU29ydGVkIEFycmF5IGluIEFzY2VuZGluZyBPcmRlcjonKQpwcmludChkYXRhKQ==
Unsorted Array
[8, 7, 2, 1, 0, 9, 6]
Sorted Array in Ascending Order:
[0, 1, 2, 6, 7, 8, 9]