Guest User

Untitled

a guest
Aug 14th, 2018
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.17 KB | None | 0 0
  1. # How to make a list into two groups where all elements of one group are
  2. # greater than or equal to the other group?
  3. #
  4. # a = [1, 2, 4, 9, 2, 3]
  5. # -> [] 1 [2, 4, 9, 2, 3]
  6. # -> [] 1 [] 2 [4, 9, 2, 3]
  7. # -> [] 1 [] 2 [3, 2, 9, 4]
  8. #
  9. #
  10. # a[i] a[j] pivot where i < j and a[i] >= pivot and a[j] < pivot
  11. # swap a[i] and a[j]
  12. # entrypoint: len(a) <= 1
  13.  
  14.  
  15. def quick_sort(a):
  16. def sort(a, start, end):
  17. if end - start <= 1:
  18. return
  19. pivot = a[start]
  20. i, j = start, end - 1
  21. while True:
  22. while a[i] < pivot and i < j:
  23. i += 1
  24. while a[j] >= pivot and j > i:
  25. j -= 1
  26. if i == j:
  27. if a[i] < pivot:
  28. i += 1
  29. j += 1
  30. elif a[i] == pivot:
  31. j -= 1
  32. i += 1
  33. break
  34. if i > j:
  35. break
  36. a[i], a[j] = a[j], a[i]
  37. i += 1
  38. j -= 1
  39. sort(a, start, j)
  40. sort(a, i, end)
  41. sort(a, 0, len(a))
  42.  
  43.  
  44. if __name__ == '__main__':
  45. a = [3, 2, 9, 10, 4, 90, 0]
  46. # 3 2 9 10 4
  47.  
  48. print('Before', a)
  49. quick_sort(a)
  50. print('After', a)
Add Comment
Please, Sign In to add comment