FilesExpand file tree

 master

/

P48_CountingSort.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

52 lines (43 loc) · 1.77 KB

 master

/

P48_CountingSort.py

Copy path

Top

File metadata and controls

• Code
• Blame

52 lines (43 loc) · 1.77 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

# Author: OMKAR PATHAK

# Approach:

# Counting sort, like radix sort and bucket sort,

# is an integer based algorithm (i.e. the values of the input

# array are assumed to be integers). Hence counting sort is

# among the fastest sorting algorithms around, in theory. The

# particular distinction for counting sort is that it creates

# a bucket for each value and keep a counter in each bucket.

# Then each time a value is encountered in the input collection,

# the appropriate counter is incremented. Because counting sort

# creates a bucket for each value, an imposing restriction is

# that the maximum value in the input array be known beforehand.

# Implementation notes:

# 1] Since the values range from 0 to k, create k+1 buckets.

# 2] To fill the buckets, iterate through the input list and

# each time a value appears, increment the counter in its

# bucket.

# 3] Now fill the input list with the compressed data in the

# buckets. Each bucket's key represents a value in the

# array. So for each bucket, from smallest key to largest,

# add the index of the bucket to the input array and

# decrease the counter in said bucket by one; until the

# counter is zero.

# Best Case O(n+k); Average Case O(n+k); Worst Case O(n+k),

# where n is the size of the input array and k means the

# values range from 0 to k.

def countingSort(myList):

maxValue = 0

for i in range(len(myList)):

if myList[i] > maxValue:

maxValue = myList[i]

buckets = [0] * (maxValue + 1)

for i in myList:

buckets[i] += 1

i = 0

for j in range(maxValue + 1):

for a in range(buckets[j]):

myList[i] = j

i += 1

return myList

if __name__ == '__main__':

sortedList = countingSort([1,23,4,5,6,7,8])

print(sortedList)