Optimized recursive_bubble_sort (#2410) · maxleaf/Python@4d0a8f2 · GitHub
Skip to content

Commit 4d0a8f2

Browse files
realDuYuanChaogithub-actions
realDuYuanChao
and
github-actions
authored
Optimized recursive_bubble_sort (TheAlgorithms#2410)
* optimized recursive_bubble_sort * Fixed doctest error due whitespace * reduce loop times for optimization * fixup! Format Python code with psf/black push Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com>
1 parent 25946e4 commit 4d0a8f2

60 files changed

Lines changed: 934 additions & 893 deletions

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎arithmetic_analysis/newton_method.py‎

Lines changed: 5 additions & 1 deletion

‎arithmetic_analysis/newton_raphson.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99

1010

1111
def newton_raphson(func: str, a: int, precision: int = 10 ** -10) -> float:
12-
""" Finds root from the point 'a' onwards by Newton-Raphson method
12+
"""Finds root from the point 'a' onwards by Newton-Raphson method
1313
>>> newton_raphson("sin(x)", 2)
1414
3.1415926536808043
1515
>>> newton_raphson("x**2 - 5*x +2", 0.4)

‎backtracking/all_permutations.py‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -13,10 +13,10 @@ def generate_all_permutations(sequence):
1313

1414
def create_state_space_tree(sequence, current_sequence, index, index_used):
1515
"""
16-
Creates a state space tree to iterate through each branch using DFS.
17-
We know that each state has exactly len(sequence) - index children.
18-
It terminates when it reaches the end of the given sequence.
19-
"""
16+
Creates a state space tree to iterate through each branch using DFS.
17+
We know that each state has exactly len(sequence) - index children.
18+
It terminates when it reaches the end of the given sequence.
19+
"""
2020

2121
if index == len(sequence):
2222
print(current_sequence)

‎backtracking/all_subsequences.py‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -13,10 +13,10 @@ def generate_all_subsequences(sequence):
1313

1414
def create_state_space_tree(sequence, current_subsequence, index):
1515
"""
16-
Creates a state space tree to iterate through each branch using DFS.
17-
We know that each state has exactly two children.
18-
It terminates when it reaches the end of the given sequence.
19-
"""
16+
Creates a state space tree to iterate through each branch using DFS.
17+
We know that each state has exactly two children.
18+
It terminates when it reaches the end of the given sequence.
19+
"""
2020

2121
if index == len(sequence):
2222
print(current_subsequence)

‎backtracking/sudoku.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -105,7 +105,7 @@ def sudoku(grid):
105105
[7, 4, 5, 2, 8, 6, 3, 1, 9]]
106106
>>> sudoku(no_solution)
107107
False
108-
"""
108+
"""
109109

110110
if is_completed(grid):
111111
return grid

‎backtracking/sum_of_subsets.py‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -19,13 +19,13 @@ def generate_sum_of_subsets_soln(nums, max_sum):
1919

2020
def create_state_space_tree(nums, max_sum, num_index, path, result, remaining_nums_sum):
2121
"""
22-
Creates a state space tree to iterate through each branch using DFS.
23-
It terminates the branching of a node when any of the two conditions
24-
given below satisfy.
25-
This algorithm follows depth-fist-search and backtracks when the node is not
26-
branchable.
22+
Creates a state space tree to iterate through each branch using DFS.
23+
It terminates the branching of a node when any of the two conditions
24+
given below satisfy.
25+
This algorithm follows depth-fist-search and backtracks when the node is not
26+
branchable.
2727
28-
"""
28+
"""
2929
if sum(path) > max_sum or (remaining_nums_sum + sum(path)) < max_sum:
3030
return
3131
if sum(path) == max_sum:

‎blockchain/modular_division.py‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -74,13 +74,13 @@ def modular_division2(a, b, n):
7474

7575
def extended_gcd(a, b):
7676
"""
77-
>>> extended_gcd(10, 6)
78-
(2, -1, 2)
77+
>>> extended_gcd(10, 6)
78+
(2, -1, 2)
7979
80-
>>> extended_gcd(7, 5)
81-
(1, -2, 3)
80+
>>> extended_gcd(7, 5)
81+
(1, -2, 3)
8282
83-
** extended_gcd function is used when d = gcd(a,b) is required in output
83+
** extended_gcd function is used when d = gcd(a,b) is required in output
8484
8585
"""
8686
assert a >= 0 and b >= 0

‎ciphers/enigma_machine2.py‎

Lines changed: 67 additions & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -17,26 +17,50 @@
1717

1818
# used alphabet --------------------------
1919
# from string.ascii_uppercase
20-
abc = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
20+
abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
2121

2222
# -------------------------- default selection --------------------------
2323
# rotors --------------------------
24-
rotor1 = 'EGZWVONAHDCLFQMSIPJBYUKXTR'
25-
rotor2 = 'FOBHMDKEXQNRAULPGSJVTYICZW'
26-
rotor3 = 'ZJXESIUQLHAVRMDOYGTNFWPBKC'
24+
rotor1 = "EGZWVONAHDCLFQMSIPJBYUKXTR"
25+
rotor2 = "FOBHMDKEXQNRAULPGSJVTYICZW"
26+
rotor3 = "ZJXESIUQLHAVRMDOYGTNFWPBKC"
2727
# reflector --------------------------
28-
reflector = {'A': 'N', 'N': 'A', 'B': 'O', 'O': 'B', 'C': 'P', 'P': 'C', 'D': 'Q',
29-
'Q': 'D', 'E': 'R', 'R': 'E', 'F': 'S', 'S': 'F', 'G': 'T', 'T': 'G',
30-
'H': 'U', 'U': 'H', 'I': 'V', 'V': 'I', 'J': 'W', 'W': 'J', 'K': 'X',
31-
'X': 'K', 'L': 'Y', 'Y': 'L', 'M': 'Z', 'Z': 'M'}
28+
reflector = {
29+
"A": "N",
30+
"N": "A",
31+
"B": "O",
32+
"O": "B",
33+
"C": "P",
34+
"P": "C",
35+
"D": "Q",
36+
"Q": "D",
37+
"E": "R",
38+
"R": "E",
39+
"F": "S",
40+
"S": "F",
41+
"G": "T",
42+
"T": "G",
43+
"H": "U",
44+
"U": "H",
45+
"I": "V",
46+
"V": "I",
47+
"J": "W",
48+
"W": "J",
49+
"K": "X",
50+
"X": "K",
51+
"L": "Y",
52+
"Y": "L",
53+
"M": "Z",
54+
"Z": "M",
55+
}
3256

3357
# -------------------------- extra rotors --------------------------
34-
rotor4 = 'RMDJXFUWGISLHVTCQNKYPBEZOA'
35-
rotor5 = 'SGLCPQWZHKXAREONTFBVIYJUDM'
36-
rotor6 = 'HVSICLTYKQUBXDWAJZOMFGPREN'
37-
rotor7 = 'RZWQHFMVDBKICJLNTUXAGYPSOE'
38-
rotor8 = 'LFKIJODBEGAMQPXVUHYSTCZRWN'
39-
rotor9 = 'KOAEGVDHXPQZMLFTYWJNBRCIUS'
58+
rotor4 = "RMDJXFUWGISLHVTCQNKYPBEZOA"
59+
rotor5 = "SGLCPQWZHKXAREONTFBVIYJUDM"
60+
rotor6 = "HVSICLTYKQUBXDWAJZOMFGPREN"
61+
rotor7 = "RZWQHFMVDBKICJLNTUXAGYPSOE"
62+
rotor8 = "LFKIJODBEGAMQPXVUHYSTCZRWN"
63+
rotor9 = "KOAEGVDHXPQZMLFTYWJNBRCIUS"
4064

4165

4266
def _validator(rotpos: tuple, rotsel: tuple, pb: str) -> tuple:
@@ -57,19 +81,22 @@ def _validator(rotpos: tuple, rotsel: tuple, pb: str) -> tuple:
5781

5882
unique_rotsel = len(set(rotsel))
5983
if unique_rotsel < 3:
60-
raise Exception(f'Please use 3 unique rotors (not {unique_rotsel})')
84+
raise Exception(f"Please use 3 unique rotors (not {unique_rotsel})")
6185

6286
# Checks if rotor positions are valid
6387
rotorpos1, rotorpos2, rotorpos3 = rotpos
6488
if not 0 < rotorpos1 <= len(abc):
65-
raise ValueError(f'First rotor position is not within range of 1..26 ('
66-
f'{rotorpos1}')
89+
raise ValueError(
90+
f"First rotor position is not within range of 1..26 (" f"{rotorpos1}"
91+
)
6792
if not 0 < rotorpos2 <= len(abc):
68-
raise ValueError(f'Second rotor position is not within range of 1..26 ('
69-
f'{rotorpos2})')
93+
raise ValueError(
94+
f"Second rotor position is not within range of 1..26 (" f"{rotorpos2})"
95+
)
7096
if not 0 < rotorpos3 <= len(abc):
71-
raise ValueError(f'Third rotor position is not within range of 1..26 ('
72-
f'{rotorpos3})')
97+
raise ValueError(
98+
f"Third rotor position is not within range of 1..26 (" f"{rotorpos3})"
99+
)
73100

74101
# Validates string and returns dict
75102
pb = _plugboard(pb)
@@ -97,21 +124,21 @@ def _plugboard(pbstring: str) -> dict:
97124
# a) is type string
98125
# b) has even length (so pairs can be made)
99126
if not isinstance(pbstring, str):
100-
raise TypeError(f'Plugboard setting isn\'t type string ({type(pbstring)})')
127+
raise TypeError(f"Plugboard setting isn't type string ({type(pbstring)})")
101128
elif len(pbstring) % 2 != 0:
102-
raise Exception(f'Odd number of symbols ({len(pbstring)})')
103-
elif pbstring == '':
129+
raise Exception(f"Odd number of symbols ({len(pbstring)})")
130+
elif pbstring == "":
104131
return {}
105132

106-
pbstring.replace(' ', '')
133+
pbstring.replace(" ", "")
107134

108135
# Checks if all characters are unique
109136
tmppbl = set()
110137
for i in pbstring:
111138
if i not in abc:
112-
raise Exception(f'\'{i}\' not in list of symbols')
139+
raise Exception(f"'{i}' not in list of symbols")
113140
elif i in tmppbl:
114-
raise Exception(f'Duplicate symbol ({i})')
141+
raise Exception(f"Duplicate symbol ({i})")
115142
else:
116143
tmppbl.add(i)
117144
del tmppbl
@@ -125,8 +152,12 @@ def _plugboard(pbstring: str) -> dict:
125152
return pb
126153

127154

128-
def enigma(text: str, rotor_position: tuple,
129-
rotor_selection: tuple = (rotor1, rotor2, rotor3), plugb: str = '') -> str:
155+
def enigma(
156+
text: str,
157+
rotor_position: tuple,
158+
rotor_selection: tuple = (rotor1, rotor2, rotor3),
159+
plugb: str = "",
160+
) -> str:
130161
"""
131162
The only difference with real-world enigma is that I allowed string input.
132163
All characters are converted to uppercase. (non-letter symbol are ignored)
@@ -179,7 +210,8 @@ def enigma(text: str, rotor_position: tuple,
179210

180211
text = text.upper()
181212
rotor_position, rotor_selection, plugboard = _validator(
182-
rotor_position, rotor_selection, plugb.upper())
213+
rotor_position, rotor_selection, plugb.upper()
214+
)
183215

184216
rotorpos1, rotorpos2, rotorpos3 = rotor_position
185217
rotor1, rotor2, rotor3 = rotor_selection
@@ -245,12 +277,12 @@ def enigma(text: str, rotor_position: tuple,
245277
return "".join(result)
246278

247279

248-
if __name__ == '__main__':
249-
message = 'This is my Python script that emulates the Enigma machine from WWII.'
280+
if __name__ == "__main__":
281+
message = "This is my Python script that emulates the Enigma machine from WWII."
250282
rotor_pos = (1, 1, 1)
251-
pb = 'pictures'
283+
pb = "pictures"
252284
rotor_sel = (rotor2, rotor4, rotor8)
253285
en = enigma(message, rotor_pos, rotor_sel, pb)
254286

255-
print('Encrypted message:', en)
256-
print('Decrypted message:', enigma(en, rotor_pos, rotor_sel, pb))
287+
print("Encrypted message:", en)
288+
print("Decrypted message:", enigma(en, rotor_pos, rotor_sel, pb))

‎ciphers/xor_cipher.py‎

Lines changed: 35 additions & 35 deletions

0 commit comments

Comments
 (0)