Python/sorts/comb_sort.py at master · PreciousJac0b/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
"""
This is pure Python implementation of comb sort algorithm.
Comb sort is a relatively simple sorting algorithm originally designed by Wlodzimierz
Dobosiewicz in 1980. It was rediscovered by Stephen Lacey and Richard Box in 1991.
Comb sort improves on bubble sort algorithm.
In bubble sort, distance (or gap) between two compared elements is always one.
Comb sort improvement is that gap can be much more than 1, in order to prevent slowing
down by small values
at the end of a list.

More info on: https://en.wikipedia.org/wiki/Comb_sort

For doctests run following command:
python -m doctest -v comb_sort.py
or
python3 -m doctest -v comb_sort.py

For manual testing run:
python comb_sort.py
"""


defcomb_sort(data: list) ->list:
"""Pure implementation of comb sort algorithm in Python
 :param data: mutable collection with comparable items
 :return: the same collection in ascending order
 Examples:
 >>> comb_sort([0, 5, 3, 2, 2])
 [0, 2, 2, 3, 5]
 >>> comb_sort([])
 []
 >>> comb_sort([99, 45, -7, 8, 2, 0, -15, 3])
 [-15, -7, 0, 2, 3, 8, 45, 99]
 """
shrink_factor=1.3
gap=len(data)
completed=False

whilenotcompleted:
# Update the gap value for a next comb
gap=int(gap/shrink_factor)
ifgap<=1:
completed=True

index=0
whileindex+gap<len(data):
ifdata[index] >data[index+gap]:
# Swap values
data[index], data[index+gap] =data[index+gap], data[index]
completed=False
index+=1

returndata


if__name__=="__main__":
importdoctest

doctest.testmod()

user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(comb_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
"""
This is pure Python implementation of comb sort algorithm.
Comb sort is a relatively simple sorting algorithm originally designed by Wlodzimierz
Dobosiewicz in 1980. It was rediscovered by Stephen Lacey and Richard Box in 1991.
Comb sort improves on bubble sort algorithm.
In bubble sort, distance (or gap) between two compared elements is always one.
Comb sort improvement is that gap can be much more than 1, in order to prevent slowing
down by small values
at the end of a list.

More info on: https://en.wikipedia.org/wiki/Comb_sort

For doctests run following command:
python -m doctest -v comb_sort.py
or
python3 -m doctest -v comb_sort.py

For manual testing run:
python comb_sort.py
"""


defcomb_sort(data: list) ->list:
"""Pure implementation of comb sort algorithm in Python
 :param data: mutable collection with comparable items
 :return: the same collection in ascending order
 Examples:
 >>> comb_sort([0, 5, 3, 2, 2])
 [0, 2, 2, 3, 5]
 >>> comb_sort([])
 []
 >>> comb_sort([99, 45, -7, 8, 2, 0, -15, 3])
 [-15, -7, 0, 2, 3, 8, 45, 99]
 """
shrink_factor=1.3
gap=len(data)
completed=False

whilenotcompleted:
# Update the gap value for a next comb
gap=int(gap/shrink_factor)
ifgap<=1:
completed=True

index=0
whileindex+gap<len(data):
ifdata[index] >data[index+gap]:
# Swap values
data[index], data[index+gap] =data[index+gap], data[index]
completed=False
index+=1

returndata


if__name__=="__main__":
importdoctest

doctest.testmod()

user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(comb_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
"""
This is pure Python implementation of comb sort algorithm.
Comb sort is a relatively simple sorting algorithm originally designed by Wlodzimierz
Dobosiewicz in 1980. It was rediscovered by Stephen Lacey and Richard Box in 1991.
Comb sort improves on bubble sort algorithm.
In bubble sort, distance (or gap) between two compared elements is always one.
Comb sort improvement is that gap can be much more than 1, in order to prevent slowing
down by small values
at the end of a list.

More info on: https://en.wikipedia.org/wiki/Comb_sort

For doctests run following command:
python -m doctest -v comb_sort.py
or
python3 -m doctest -v comb_sort.py

For manual testing run:
python comb_sort.py
"""


defcomb_sort(data: list) ->list:
"""Pure implementation of comb sort algorithm in Python
 :param data: mutable collection with comparable items
 :return: the same collection in ascending order
 Examples:
 >>> comb_sort([0, 5, 3, 2, 2])
 [0, 2, 2, 3, 5]
 >>> comb_sort([])
 []
 >>> comb_sort([99, 45, -7, 8, 2, 0, -15, 3])
 [-15, -7, 0, 2, 3, 8, 45, 99]
 """
shrink_factor=1.3
gap=len(data)
completed=False

whilenotcompleted:
# Update the gap value for a next comb
gap=int(gap/shrink_factor)
ifgap<=1:
completed=True

index=0
whileindex+gap<len(data):
ifdata[index] >data[index+gap]:
# Swap values
data[index], data[index+gap] =data[index+gap], data[index]
completed=False
index+=1

returndata


if__name__=="__main__":
importdoctest

doctest.testmod()

user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(comb_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
"""
This is pure Python implementation of comb sort algorithm.
Comb sort is a relatively simple sorting algorithm originally designed by Wlodzimierz
Dobosiewicz in 1980. It was rediscovered by Stephen Lacey and Richard Box in 1991.
Comb sort improves on bubble sort algorithm.
In bubble sort, distance (or gap) between two compared elements is always one.
Comb sort improvement is that gap can be much more than 1, in order to prevent slowing
down by small values
at the end of a list.

More info on: https://en.wikipedia.org/wiki/Comb_sort

For doctests run following command:
python -m doctest -v comb_sort.py
or
python3 -m doctest -v comb_sort.py

For manual testing run:
python comb_sort.py
"""


defcomb_sort(data: list) ->list:
"""Pure implementation of comb sort algorithm in Python
 :param data: mutable collection with comparable items
 :return: the same collection in ascending order
 Examples:
 >>> comb_sort([0, 5, 3, 2, 2])
 [0, 2, 2, 3, 5]
 >>> comb_sort([])
 []
 >>> comb_sort([99, 45, -7, 8, 2, 0, -15, 3])
 [-15, -7, 0, 2, 3, 8, 45, 99]
 """
shrink_factor=1.3
gap=len(data)
completed=False

whilenotcompleted:
# Update the gap value for a next comb
gap=int(gap/shrink_factor)
ifgap<=1:
completed=True

index=0
whileindex+gap<len(data):
ifdata[index] >data[index+gap]:
# Swap values
data[index], data[index+gap] =data[index+gap], data[index]
completed=False
index+=1

returndata


if__name__=="__main__":
importdoctest

doctest.testmod()

user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(comb_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
"""
This is pure Python implementation of comb sort algorithm.
Comb sort is a relatively simple sorting algorithm originally designed by Wlodzimierz
Dobosiewicz in 1980. It was rediscovered by Stephen Lacey and Richard Box in 1991.
Comb sort improves on bubble sort algorithm.
In bubble sort, distance (or gap) between two compared elements is always one.
Comb sort improvement is that gap can be much more than 1, in order to prevent slowing
down by small values
at the end of a list.

More info on: https://en.wikipedia.org/wiki/Comb_sort

For doctests run following command:
python -m doctest -v comb_sort.py
or
python3 -m doctest -v comb_sort.py

For manual testing run:
python comb_sort.py
"""


defcomb_sort(data: list) ->list:
"""Pure implementation of comb sort algorithm in Python
 :param data: mutable collection with comparable items
 :return: the same collection in ascending order
 Examples:
 >>> comb_sort([0, 5, 3, 2, 2])
 [0, 2, 2, 3, 5]
 >>> comb_sort([])
 []
 >>> comb_sort([99, 45, -7, 8, 2, 0, -15, 3])
 [-15, -7, 0, 2, 3, 8, 45, 99]
 """
shrink_factor=1.3
gap=len(data)
completed=False

whilenotcompleted:
# Update the gap value for a next comb
gap=int(gap/shrink_factor)
ifgap<=1:
completed=True

index=0
whileindex+gap<len(data):
ifdata[index] >data[index+gap]:
# Swap values
data[index], data[index+gap] =data[index+gap], data[index]
completed=False
index+=1

returndata


if__name__=="__main__":
importdoctest

doctest.testmod()

user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(comb_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
"""
This is pure Python implementation of comb sort algorithm.
Comb sort is a relatively simple sorting algorithm originally designed by Wlodzimierz
Dobosiewicz in 1980. It was rediscovered by Stephen Lacey and Richard Box in 1991.
Comb sort improves on bubble sort algorithm.
In bubble sort, distance (or gap) between two compared elements is always one.
Comb sort improvement is that gap can be much more than 1, in order to prevent slowing
down by small values
at the end of a list.

More info on: https://en.wikipedia.org/wiki/Comb_sort

For doctests run following command:
python -m doctest -v comb_sort.py
or
python3 -m doctest -v comb_sort.py

For manual testing run:
python comb_sort.py
"""


defcomb_sort(data: list) ->list:
"""Pure implementation of comb sort algorithm in Python
 :param data: mutable collection with comparable items
 :return: the same collection in ascending order
 Examples:
 >>> comb_sort([0, 5, 3, 2, 2])
 [0, 2, 2, 3, 5]
 >>> comb_sort([])
 []
 >>> comb_sort([99, 45, -7, 8, 2, 0, -15, 3])
 [-15, -7, 0, 2, 3, 8, 45, 99]
 """
shrink_factor=1.3
gap=len(data)
completed=False

whilenotcompleted:
# Update the gap value for a next comb
gap=int(gap/shrink_factor)
ifgap<=1:
completed=True

index=0
whileindex+gap<len(data):
ifdata[index] >data[index+gap]:
# Swap values
data[index], data[index+gap] =data[index+gap], data[index]
completed=False
index+=1

returndata


if__name__=="__main__":
importdoctest

doctest.testmod()

user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(comb_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
"""
This is pure Python implementation of comb sort algorithm.
Comb sort is a relatively simple sorting algorithm originally designed by Wlodzimierz
Dobosiewicz in 1980. It was rediscovered by Stephen Lacey and Richard Box in 1991.
Comb sort improves on bubble sort algorithm.
In bubble sort, distance (or gap) between two compared elements is always one.
Comb sort improvement is that gap can be much more than 1, in order to prevent slowing
down by small values
at the end of a list.

More info on: https://en.wikipedia.org/wiki/Comb_sort

For doctests run following command:
python -m doctest -v comb_sort.py
or
python3 -m doctest -v comb_sort.py

For manual testing run:
python comb_sort.py
"""


defcomb_sort(data: list) ->list:
"""Pure implementation of comb sort algorithm in Python
 :param data: mutable collection with comparable items
 :return: the same collection in ascending order
 Examples:
 >>> comb_sort([0, 5, 3, 2, 2])
 [0, 2, 2, 3, 5]
 >>> comb_sort([])
 []
 >>> comb_sort([99, 45, -7, 8, 2, 0, -15, 3])
 [-15, -7, 0, 2, 3, 8, 45, 99]
 """
shrink_factor=1.3
gap=len(data)
completed=False

whilenotcompleted:
# Update the gap value for a next comb
gap=int(gap/shrink_factor)
ifgap<=1:
completed=True

index=0
whileindex+gap<len(data):
ifdata[index] >data[index+gap]:
# Swap values
data[index], data[index+gap] =data[index+gap], data[index]
completed=False
index+=1

returndata


if__name__=="__main__":
importdoctest

doctest.testmod()

user_input=input("Enter numbers separated by a comma:\n").strip()
unsorted= [int(item) foriteminuser_input.split(",")]
print(comb_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
"""
This is pure Python implementation of comb sort algorithm.
Comb sort is a relatively simple sorting algorithm originally designed by Wlodzimierz
Dobosiewicz in 1980. It was rediscovered by Stephen Lacey and Richard Box in 1991.
Comb sort improves on bubble sort algorithm.
In bubble sort, distance (or gap) between two compared elements is always one.
Comb sort improvement is that gap can be much more than 1, in order to prevent slowing
down by small values
at the end of a list.

More info on: https://en.wikipedia.org/wiki/Comb_sort

For doctests run following command:
python -m doctest -v comb_sort.py
or
python3 -m doctest -v comb_sort.py

For manual testing run:
python comb_sort.py
"""


defcomb_sort(data: list) ->list:
"""Pure implementation of comb sort algorithm in Python
 :param data: mutable collection with comparable items
 :return: the same collection in ascending order
 Examples:
 >>> comb_sort([0, 5, 3, 2, 2])
 [0, 2, 2, 3, 5]
 >>> comb_sort([])
 []
 >>> comb_sort([99, 45, -7, 8, 2, 0, -15, 3])
 [-15, -7, 0, 2, 3, 8, 45, 99]
 """
shrink_factor=1.3
gap=len(data)
completed=False

whilenotcompleted:
# Update the gap value for a next comb
gap=int(gap/shrink_factor)
ifgap<=1:
completed=True

index=0
whileindex+gap<len(data):
ifdata[index] >data[index+gap]:
# Swap values
data[index], data[index+gap] =data[index+gap], data[index]
completed=False
index+=1

returndata


if__name__=="__main__":
importdoctest

doctest.testmod()

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