Python/sorts/counting_sort.py at master · manmita/Python · GitHub

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
"""
This is pure Python implementation of counting sort algorithm
For doctests run following command:
python -m doctest -v counting_sort.py
or
python3 -m doctest -v counting_sort.py
For manual testing run:
python counting_sort.py
"""


defcounting_sort(collection):
"""Pure implementation of counting sort algorithm in Python
 :param collection: some mutable ordered collection with heterogeneous
 comparable items inside
 :return: the same collection ordered by ascending
 Examples:
 >>> counting_sort([0, 5, 3, 2, 2])
 [0, 2, 2, 3, 5]
 >>> counting_sort([])
 []
 >>> counting_sort([-2, -5, -45])
 [-45, -5, -2]
 """
# if the collection is empty, returns empty
ifcollection== []:
return []

# get some information about the collection
coll_len=len(collection)
coll_max=max(collection)
coll_min=min(collection)

# create the counting array
counting_arr_length=coll_max+1-coll_min
counting_arr= [0] *counting_arr_length

# count how much a number appears in the collection
fornumberincollection:
counting_arr[number-coll_min] +=1

# sum each position with it's predecessors. now, counting_arr[i] tells
# us how many elements <= i has in the collection
foriinrange(1, counting_arr_length):
counting_arr[i] =counting_arr[i] +counting_arr[i-1]

# create the output collection
ordered= [0] *coll_len

# place the elements in the output, respecting the original order (stable
# sort) from end to begin, updating counting_arr
foriinreversed(range(coll_len)):
ordered[counting_arr[collection[i] -coll_min] -1] =collection[i]
counting_arr[collection[i] -coll_min] -=1

returnordered


defcounting_sort_string(string):
"""
 >>> counting_sort_string("thisisthestring")
 'eghhiiinrsssttt'
 """
return"".join([chr(i) foriincounting_sort([ord(c) forcinstring])])


if__name__=="__main__":
# Test string sort
assertcounting_sort_string("thisisthestring") =="eghhiiinrsssttt"

user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(counting_sort(unsorted))
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
"""
This is pure Python implementation of counting sort algorithm
For doctests run following command:
python -m doctest -v counting_sort.py
or
python3 -m doctest -v counting_sort.py
For manual testing run:
python counting_sort.py
"""


defcounting_sort(collection):
"""Pure implementation of counting sort algorithm in Python
 :param collection: some mutable ordered collection with heterogeneous
 comparable items inside
 :return: the same collection ordered by ascending
 Examples:
 >>> counting_sort([0, 5, 3, 2, 2])
 [0, 2, 2, 3, 5]
 >>> counting_sort([])
 []
 >>> counting_sort([-2, -5, -45])
 [-45, -5, -2]
 """
# if the collection is empty, returns empty
ifcollection== []:
return []

# get some information about the collection
coll_len=len(collection)
coll_max=max(collection)
coll_min=min(collection)

# create the counting array
counting_arr_length=coll_max+1-coll_min
counting_arr= [0] *counting_arr_length

# count how much a number appears in the collection
fornumberincollection:
counting_arr[number-coll_min] +=1

# sum each position with it's predecessors. now, counting_arr[i] tells
# us how many elements <= i has in the collection
foriinrange(1, counting_arr_length):
counting_arr[i] =counting_arr[i] +counting_arr[i-1]

# create the output collection
ordered= [0] *coll_len

# place the elements in the output, respecting the original order (stable
# sort) from end to begin, updating counting_arr
foriinreversed(range(coll_len)):
ordered[counting_arr[collection[i] -coll_min] -1] =collection[i]
counting_arr[collection[i] -coll_min] -=1

returnordered


defcounting_sort_string(string):
"""
 >>> counting_sort_string("thisisthestring")
 'eghhiiinrsssttt'
 """
return"".join([chr(i) foriincounting_sort([ord(c) forcinstring])])


if__name__=="__main__":
# Test string sort
assertcounting_sort_string("thisisthestring") =="eghhiiinrsssttt"

user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(counting_sort(unsorted))
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
"""
This is pure Python implementation of counting sort algorithm
For doctests run following command:
python -m doctest -v counting_sort.py
or
python3 -m doctest -v counting_sort.py
For manual testing run:
python counting_sort.py
"""


defcounting_sort(collection):
"""Pure implementation of counting sort algorithm in Python
 :param collection: some mutable ordered collection with heterogeneous
 comparable items inside
 :return: the same collection ordered by ascending
 Examples:
 >>> counting_sort([0, 5, 3, 2, 2])
 [0, 2, 2, 3, 5]
 >>> counting_sort([])
 []
 >>> counting_sort([-2, -5, -45])
 [-45, -5, -2]
 """
# if the collection is empty, returns empty
ifcollection== []:
return []

# get some information about the collection
coll_len=len(collection)
coll_max=max(collection)
coll_min=min(collection)

# create the counting array
counting_arr_length=coll_max+1-coll_min
counting_arr= [0] *counting_arr_length

# count how much a number appears in the collection
fornumberincollection:
counting_arr[number-coll_min] +=1

# sum each position with it's predecessors. now, counting_arr[i] tells
# us how many elements <= i has in the collection
foriinrange(1, counting_arr_length):
counting_arr[i] =counting_arr[i] +counting_arr[i-1]

# create the output collection
ordered= [0] *coll_len

# place the elements in the output, respecting the original order (stable
# sort) from end to begin, updating counting_arr
foriinreversed(range(coll_len)):
ordered[counting_arr[collection[i] -coll_min] -1] =collection[i]
counting_arr[collection[i] -coll_min] -=1

returnordered


defcounting_sort_string(string):
"""
 >>> counting_sort_string("thisisthestring")
 'eghhiiinrsssttt'
 """
return"".join([chr(i) foriincounting_sort([ord(c) forcinstring])])


if__name__=="__main__":
# Test string sort
assertcounting_sort_string("thisisthestring") =="eghhiiinrsssttt"

user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(counting_sort(unsorted))
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
"""
This is pure Python implementation of counting sort algorithm
For doctests run following command:
python -m doctest -v counting_sort.py
or
python3 -m doctest -v counting_sort.py
For manual testing run:
python counting_sort.py
"""


defcounting_sort(collection):
"""Pure implementation of counting sort algorithm in Python
 :param collection: some mutable ordered collection with heterogeneous
 comparable items inside
 :return: the same collection ordered by ascending
 Examples:
 >>> counting_sort([0, 5, 3, 2, 2])
 [0, 2, 2, 3, 5]
 >>> counting_sort([])
 []
 >>> counting_sort([-2, -5, -45])
 [-45, -5, -2]
 """
# if the collection is empty, returns empty
ifcollection== []:
return []

# get some information about the collection
coll_len=len(collection)
coll_max=max(collection)
coll_min=min(collection)

# create the counting array
counting_arr_length=coll_max+1-coll_min
counting_arr= [0] *counting_arr_length

# count how much a number appears in the collection
fornumberincollection:
counting_arr[number-coll_min] +=1

# sum each position with it's predecessors. now, counting_arr[i] tells
# us how many elements <= i has in the collection
foriinrange(1, counting_arr_length):
counting_arr[i] =counting_arr[i] +counting_arr[i-1]

# create the output collection
ordered= [0] *coll_len

# place the elements in the output, respecting the original order (stable
# sort) from end to begin, updating counting_arr
foriinreversed(range(coll_len)):
ordered[counting_arr[collection[i] -coll_min] -1] =collection[i]
counting_arr[collection[i] -coll_min] -=1

returnordered


defcounting_sort_string(string):
"""
 >>> counting_sort_string("thisisthestring")
 'eghhiiinrsssttt'
 """
return"".join([chr(i) foriincounting_sort([ord(c) forcinstring])])


if__name__=="__main__":
# Test string sort
assertcounting_sort_string("thisisthestring") =="eghhiiinrsssttt"

user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(counting_sort(unsorted))
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
"""
This is pure Python implementation of counting sort algorithm
For doctests run following command:
python -m doctest -v counting_sort.py
or
python3 -m doctest -v counting_sort.py
For manual testing run:
python counting_sort.py
"""


defcounting_sort(collection):
"""Pure implementation of counting sort algorithm in Python
 :param collection: some mutable ordered collection with heterogeneous
 comparable items inside
 :return: the same collection ordered by ascending
 Examples:
 >>> counting_sort([0, 5, 3, 2, 2])
 [0, 2, 2, 3, 5]
 >>> counting_sort([])
 []
 >>> counting_sort([-2, -5, -45])
 [-45, -5, -2]
 """
# if the collection is empty, returns empty
ifcollection== []:
return []

# get some information about the collection
coll_len=len(collection)
coll_max=max(collection)
coll_min=min(collection)

# create the counting array
counting_arr_length=coll_max+1-coll_min
counting_arr= [0] *counting_arr_length

# count how much a number appears in the collection
fornumberincollection:
counting_arr[number-coll_min] +=1

# sum each position with it's predecessors. now, counting_arr[i] tells
# us how many elements <= i has in the collection
foriinrange(1, counting_arr_length):
counting_arr[i] =counting_arr[i] +counting_arr[i-1]

# create the output collection
ordered= [0] *coll_len

# place the elements in the output, respecting the original order (stable
# sort) from end to begin, updating counting_arr
foriinreversed(range(coll_len)):
ordered[counting_arr[collection[i] -coll_min] -1] =collection[i]
counting_arr[collection[i] -coll_min] -=1

returnordered


defcounting_sort_string(string):
"""
 >>> counting_sort_string("thisisthestring")
 'eghhiiinrsssttt'
 """
return"".join([chr(i) foriincounting_sort([ord(c) forcinstring])])


if__name__=="__main__":
# Test string sort
assertcounting_sort_string("thisisthestring") =="eghhiiinrsssttt"

user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(counting_sort(unsorted))
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
"""
This is pure Python implementation of counting sort algorithm
For doctests run following command:
python -m doctest -v counting_sort.py
or
python3 -m doctest -v counting_sort.py
For manual testing run:
python counting_sort.py
"""


defcounting_sort(collection):
"""Pure implementation of counting sort algorithm in Python
 :param collection: some mutable ordered collection with heterogeneous
 comparable items inside
 :return: the same collection ordered by ascending
 Examples:
 >>> counting_sort([0, 5, 3, 2, 2])
 [0, 2, 2, 3, 5]
 >>> counting_sort([])
 []
 >>> counting_sort([-2, -5, -45])
 [-45, -5, -2]
 """
# if the collection is empty, returns empty
ifcollection== []:
return []

# get some information about the collection
coll_len=len(collection)
coll_max=max(collection)
coll_min=min(collection)

# create the counting array
counting_arr_length=coll_max+1-coll_min
counting_arr= [0] *counting_arr_length

# count how much a number appears in the collection
fornumberincollection:
counting_arr[number-coll_min] +=1

# sum each position with it's predecessors. now, counting_arr[i] tells
# us how many elements <= i has in the collection
foriinrange(1, counting_arr_length):
counting_arr[i] =counting_arr[i] +counting_arr[i-1]

# create the output collection
ordered= [0] *coll_len

# place the elements in the output, respecting the original order (stable
# sort) from end to begin, updating counting_arr
foriinreversed(range(coll_len)):
ordered[counting_arr[collection[i] -coll_min] -1] =collection[i]
counting_arr[collection[i] -coll_min] -=1

returnordered


defcounting_sort_string(string):
"""
 >>> counting_sort_string("thisisthestring")
 'eghhiiinrsssttt'
 """
return"".join([chr(i) foriincounting_sort([ord(c) forcinstring])])


if__name__=="__main__":
# Test string sort
assertcounting_sort_string("thisisthestring") =="eghhiiinrsssttt"

user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(counting_sort(unsorted))
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
"""
This is pure Python implementation of counting sort algorithm
For doctests run following command:
python -m doctest -v counting_sort.py
or
python3 -m doctest -v counting_sort.py
For manual testing run:
python counting_sort.py
"""


defcounting_sort(collection):
"""Pure implementation of counting sort algorithm in Python
 :param collection: some mutable ordered collection with heterogeneous
 comparable items inside
 :return: the same collection ordered by ascending
 Examples:
 >>> counting_sort([0, 5, 3, 2, 2])
 [0, 2, 2, 3, 5]
 >>> counting_sort([])
 []
 >>> counting_sort([-2, -5, -45])
 [-45, -5, -2]
 """
# if the collection is empty, returns empty
ifcollection== []:
return []

# get some information about the collection
coll_len=len(collection)
coll_max=max(collection)
coll_min=min(collection)

# create the counting array
counting_arr_length=coll_max+1-coll_min
counting_arr= [0] *counting_arr_length

# count how much a number appears in the collection
fornumberincollection:
counting_arr[number-coll_min] +=1

# sum each position with it's predecessors. now, counting_arr[i] tells
# us how many elements <= i has in the collection
foriinrange(1, counting_arr_length):
counting_arr[i] =counting_arr[i] +counting_arr[i-1]

# create the output collection
ordered= [0] *coll_len

# place the elements in the output, respecting the original order (stable
# sort) from end to begin, updating counting_arr
foriinreversed(range(coll_len)):
ordered[counting_arr[collection[i] -coll_min] -1] =collection[i]
counting_arr[collection[i] -coll_min] -=1

returnordered


defcounting_sort_string(string):
"""
 >>> counting_sort_string("thisisthestring")
 'eghhiiinrsssttt'
 """
return"".join([chr(i) foriincounting_sort([ord(c) forcinstring])])


if__name__=="__main__":
# Test string sort
assertcounting_sort_string("thisisthestring") =="eghhiiinrsssttt"

user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(counting_sort(unsorted))
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
"""
This is pure Python implementation of counting sort algorithm
For doctests run following command:
python -m doctest -v counting_sort.py
or
python3 -m doctest -v counting_sort.py
For manual testing run:
python counting_sort.py
"""


defcounting_sort(collection):
"""Pure implementation of counting sort algorithm in Python
 :param collection: some mutable ordered collection with heterogeneous
 comparable items inside
 :return: the same collection ordered by ascending
 Examples:
 >>> counting_sort([0, 5, 3, 2, 2])
 [0, 2, 2, 3, 5]
 >>> counting_sort([])
 []
 >>> counting_sort([-2, -5, -45])
 [-45, -5, -2]
 """
# if the collection is empty, returns empty
ifcollection== []:
return []

# get some information about the collection
coll_len=len(collection)
coll_max=max(collection)
coll_min=min(collection)

# create the counting array
counting_arr_length=coll_max+1-coll_min
counting_arr= [0] *counting_arr_length

# count how much a number appears in the collection
fornumberincollection:
counting_arr[number-coll_min] +=1

# sum each position with it's predecessors. now, counting_arr[i] tells
# us how many elements <= i has in the collection
foriinrange(1, counting_arr_length):
counting_arr[i] =counting_arr[i] +counting_arr[i-1]

# create the output collection
ordered= [0] *coll_len

# place the elements in the output, respecting the original order (stable
# sort) from end to begin, updating counting_arr
foriinreversed(range(coll_len)):
ordered[counting_arr[collection[i] -coll_min] -1] =collection[i]
counting_arr[collection[i] -coll_min] -=1

returnordered


defcounting_sort_string(string):
"""
 >>> counting_sort_string("thisisthestring")
 'eghhiiinrsssttt'
 """
return"".join([chr(i) foriincounting_sort([ord(c) forcinstring])])


if__name__=="__main__":
# Test string sort
assertcounting_sort_string("thisisthestring") =="eghhiiinrsssttt"

user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(counting_sort(unsorted))