Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # How to make a list into two groups where all elements of one group are
- # greater than or equal to the other group?
- #
- # a = [1, 2, 4, 9, 2, 3]
- # -> [] 1 [2, 4, 9, 2, 3]
- # -> [] 1 [] 2 [4, 9, 2, 3]
- # -> [] 1 [] 2 [3, 2, 9, 4]
- #
- #
- # a[i] a[j] pivot where i < j and a[i] >= pivot and a[j] < pivot
- # swap a[i] and a[j]
- # entrypoint: len(a) <= 1
- def quick_sort(a):
- def sort(a, start, end):
- if end - start <= 1:
- return
- pivot = a[start]
- i, j = start, end - 1
- while True:
- while a[i] < pivot and i < j:
- i += 1
- while a[j] >= pivot and j > i:
- j -= 1
- if i == j:
- if a[i] < pivot:
- i += 1
- j += 1
- elif a[i] == pivot:
- j -= 1
- i += 1
- break
- if i > j:
- break
- a[i], a[j] = a[j], a[i]
- i += 1
- j -= 1
- sort(a, start, j)
- sort(a, i, end)
- sort(a, 0, len(a))
- if __name__ == '__main__':
- a = [3, 2, 9, 10, 4, 90, 0]
- # 3 2 9 10 4
- print('Before', a)
- quick_sort(a)
- print('After', a)
Add Comment
Please, Sign In to add comment