FilesExpand file tree

 master

/

quick_sort.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

32 lines (27 loc) · 1.05 KB

 master

/

quick_sort.py

Copy path

Top

File metadata and controls

• Code
• Blame

32 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

def quick_sort(arr, simulation=False):

""" Quick sort

Complexity: best O(n log(n)) avg O(n log(n)), worst O(N^2)

"""

iteration = 0

if simulation:

print("iteration",iteration,":",*arr)

arr, _ = quick_sort_recur(arr, 0, len(arr) - 1, iteration, simulation)

return arr

def quick_sort_recur(arr, first, last, iteration, simulation):

if first < last:

pos = partition(arr, first, last)

# Start our two recursive calls

if simulation:

iteration = iteration + 1

print("iteration",iteration,":",*arr)

_, iteration = quick_sort_recur(arr, first, pos - 1, iteration, simulation)

_, iteration = quick_sort_recur(arr, pos + 1, last, iteration, simulation)

return arr, iteration

def partition(arr, first, last):

wall = first

for pos in range(first, last):

if arr[pos] < arr[last]: # last is the pivot

arr[pos], arr[wall] = arr[wall], arr[pos]

wall += 1

arr[wall], arr[last] = arr[last], arr[wall]

return wall