FilesExpand file tree

 master

/

Quick_Sort.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

41 lines (33 loc) · 1.25 KB

 master

/

Quick_Sort.py

Copy path

Top

File metadata and controls

• Code
• Blame

41 lines (33 loc) · 1.25 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

34

35

36

37

38

39

40

41

def partition(nums, low, high):

# We select the middle element to be the pivot. Some implementations select

# the first element or the last element. Sometimes the median value becomes

# the pivot, or a random one. There are many more strategies that can be

# chosen or created.

pivot = nums[(low + high) // 2]

i = low - 1

j = high + 1

while True:

i += 1

while nums[i] < pivot:

i += 1

j -= 1

while nums[j] > pivot:

j -= 1

if i >= j:

return j

# If an element at i (on the left of the pivot) is larger than the

# element at j (on right right of the pivot), then swap them

nums[i], nums[j] = nums[j], nums[i]

def quick_sort(nums):

# Create a helper function that will be called recursively

def _quick_sort(items, low, high):

if low < high:

# This is the index after the pivot, where our lists are split

split_index = partition(items, low, high)

_quick_sort(items, low, split_index)

_quick_sort(items, split_index + 1, high)

_quick_sort(nums, 0, len(nums) - 1)

# Verify it works

random_list_of_nums = [22, 5, 1, 18, 99]

quick_sort(random_list_of_nums)

print(random_list_of_nums)