FilesExpand file tree

 master

/

quick.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

55 lines (44 loc) · 1.11 KB

 master

/

quick.py

Copy path

Top

File metadata and controls

• Code
• Blame

55 lines (44 loc) · 1.11 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

42

43

44

45

46

47

48

49

50

51

52

53

54

55

#!/bin/env python

# -*- coding:utf-8 -*-

# This script only contains the implement of quicksort

import random

def sort(data):

__sort(data, 0, len(data) - 1)

def __swap(data, lo, hi):

data[lo], data[hi] = data[hi], data[lo]

def __sort(data, lo, hi):

if lo >= hi:

return

key = __partition(data, lo, hi)

__sort(data, lo, key - 1)

__sort(data, key + 1, hi)

def __partition(data, lo, hi):

'''partition array'''

i = lo

j = hi

v = data[lo] # slicing element

while True:

# find one element that larger than v scan from left to right(→)

i += 1

while data[i] < v:

if i == hi:

break

i += 1

# find one element that smaller than v scan from right to left(←)

while v < data[j]:

if j == lo:

break

j -= 1

if i >= j:

break

__swap(data, i, j)

__swap(data, lo, j)

return j

def main():

data = [_ for _ in range(20)]

random.shuffle(data)

print(data)

sort(data)

print(data)

if __name__ == '__main__':

main()