FilesExpand file tree

 master

/

counting_sort.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

36 lines (32 loc) · 1.25 KB

 master

/

counting_sort.py

Copy path

Top

File metadata and controls

• Code
• Blame

36 lines (32 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

def counting_sort(arr):

"""

Counting_sort

Sorting a array which has no element greater than k

Creating a new temp_arr,where temp_arr[i] contain the number of

element less than or equal to i in the arr

Then placing the number i into a correct position in the result_arr

return the result_arr

Complexity: 0(n)

"""

m = min(arr)

# in case there are negative elements, change the array to all positive element

different = 0

if m < 0:

# save the change, so that we can convert the array back to all positive number

different = -m

for i in range(len(arr)):

arr[i] += -m

k = max(arr)

temp_arr = [0] * (k + 1)

for i in range(0, len(arr)):

temp_arr[arr[i]] = temp_arr[arr[i]] + 1

# temp_array[i] contain the times the number i appear in arr

for i in range(1, k + 1):

temp_arr[i] = temp_arr[i] + temp_arr[i - 1]

# temp_array[i] contain the number of element less than or equal i in arr

result_arr = arr.copy()

# creating a result_arr an put the element in a correct positon

for i in range(len(arr) - 1, -1, -1):

result_arr[temp_arr[arr[i]] - 1] = arr[i] - different

temp_arr[arr[i]] = temp_arr[arr[i]] - 1

return result_arr