FilesExpand file tree

 patch-1

/

random_pivot_quick_sort.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

33 lines (27 loc) · 1.05 KB

 patch-1

/

random_pivot_quick_sort.py

Copy path

Top

File metadata and controls

• Code
• Blame

33 lines (27 loc) · 1.05 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

"""

Picks the random index as the pivot

"""

import random

def partition(A, left_index, right_index):

pivot = A[left_index]

i = left_index + 1

for j in range(left_index + 1, right_index):

if A[j] < pivot:

A[j], A[i] = A[i], A[j]

i += 1

A[left_index], A[i - 1] = A[i - 1], A[left_index]

return i - 1

def quick_sort_random(A, left, right):

if left < right:

pivot = random.randint(left, right - 1)

A[pivot], A[left] = A[left], A[pivot] #switches the pivot with the left most bound

pivot_index = partition(A, left, right)

quick_sort_random(A, left, pivot_index) #recursive quicksort to the left of the pivot point

quick_sort_random(A, pivot_index + 1, right) #recursive quicksort to the right of the pivot point

def main():

user_input = input('Enter numbers separated by a comma:\n').strip()

arr = [int(item) for item in user_input.split(',')]

quick_sort_random(arr, 0, len(arr))

print(arr)

if __name__ == "__main__":

main()