Python/sorts/cocktail_shaker_sort.py

Python/sorts/counting_sort.py

assert “e” == “e”
assert “e” == “a”
Traceback (most recent call last):
File “<pyshell#88>”, line 1, in
assert “e” == “a”
AssertionError

python中使用函数ord(),可以字符转换为对应数值,使用函数chr可以将数值转换为对应字符

string=“thisisthestring”
[ord© for c in string]
[116, 104, 105, 115, 105, 115, 116, 104, 101, 115, 116, 114, 105, 110, 103]

#list的生成

[0]*10
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

[0]*18
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

[1]*10
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

counting_arr
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

counting_arr[116 - 101] += 1
counting_arr
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

counting_arr[104 - 101] += 1
counting_arr
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

counting_arr[105 - 101] += 1
counting_arr
[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

counting_arr[115 - 101] += 1
counting_arr
[0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]

counting_arr[3] += 1
counting_arr
[0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]

counting_arr[3] += 1
counting_arr
[0, 0, 0, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]

a=0
a+=1
a
1

a+=1
a
2

Python/sorts/cycle_sort.py

string
‘thisisthestring’

string[:-1]
‘thisisthestrin’

Python/sorts/heap_sort.py
##函数套函数

unsorted
[4.0, -1.0, -8.0, 7.0]

collection=unsorted
def merge_sort(collection):
def merge(left,right):#这里定义函数，函数套函数就是为了给下面的参数内部调用
result=[]
while left and right:
result.append((left if left[0]<=right[0] else right).pop(0))
return result+left+right
if len(collection)<=1:
return collection
mid=len(collection)//2
return merge(merge_sort(collection[:mid]),merge_sort(collection[mid:]))###这里调用merge

s=merge_sort(collection)
s
[-8.0, -1.0, 4.0, 7.0]

mid = len(collection) // 2
mid
2

collection[:mid]
[-1.0, 4.0]

collection[mid:]
[-8.0, 7.0]

collection[:2]
[-1.0, 4.0]

collection[2:]
[-8.0, 7.0]

left
[-1.0, 4.0]

right
[-8.0, 7.0]

left if left[0]<=right[0] else right
[-8.0, 7.0]

left if left[0]>=right[0] else right
[-1.0, 4.0]

(left if left[0] <= right[0] else right).pop(0)
-8.0

result=[]
result.append((left if left[0]<=right[0] else right).pop(0))
result
[-8.0]

Python/sorts/normal_distribution_quick_sort.md

arr=[0, 10, 15, 3, 2, 9, 14, 13]
cur = len(arr)
arr[0:cur]
[0, 10, 15, 3, 2, 9, 14, 13]

max(arr[0:cur])
15

max(arr)
15

arr.index(max(arr[0:cur]))
2

[list() for _ in range( 5 )]
[[], [], [], [], []]

[list() for _ in range( 5 )][1]
[]

[list() for _ in range( 5 )][1].append(5)
[list() for _ in range( 5 )]
[[], [], [], [], []]

buckets = [list() for _ in range( 5 )]
buckets
[[], [], [], [], []]

buckets[1].append(3)
buckets
[[], [3], [], [], []]

Python/sorts/random_normal_distribution_quicksort.py

from tempfile import TemporaryFile
outfile = TemporaryFile()
outfile
<tempfile._TemporaryFileWrapper object at 0x036AC550>

outfile.seek(0)
0

import numpy as np

from random import randint
M = np.load(outfile)
Traceback (most recent call last):
File “<pyshell#19>”, line 1, in
M = np.load(outfile)
####缺少np.save(outfile, X)，所以上面不能成功load（outfile）
#######从新

outfile = TemporaryFile()
p = 100 # 1000 elements are to be sorted
mu, sigma = 0, 1 # mean and standard deviation
X = np.random.normal(mu, sigma, p)
np.save(outfile, X)
print(X)
[ 6.78274090e-01 -8.52825948e-01 -6.03075501e-01 -1.00420005e+00
-7.96532326e-01 -1.65382101e-01 1.43116450e-01 -1.97848426e-01
-1.33776608e+00 1.23098969e+00 -5.90892251e-01 2.25601202e-02
8.78504619e-01 -2.12425011e-01 -5.30371020e-02 4.95412246e-04
5.93632659e-01 1.57925727e+00 -1.56882239e-02 -6.29695805e-01
1.24938150e-01 8.80617366e-01 -7.99251066e-01 2.38656180e+00
3.32651204e-01 -3.57059719e-01 1.61777246e-01 -6.87525484e-01
8.93905681e-02 3.62200207e-01 4.91261620e-01 -5.67746134e-01
1.48533911e+00 4.29460700e-02 -5.28135571e-01 3.09401599e-01
1.45018211e+00 3.16740944e-03 -8.63631498e-01 6.35933960e-01
-7.16705078e-01 1.66224636e+00 9.34081343e-01 -1.32380505e+00
-4.16166793e-01 1.11065891e+00 -4.16605130e-03 2.71138500e-01
1.22826598e-01 -4.06749298e-01 6.62851533e-01 -7.70384316e-01
-4.32017494e-01 -2.44006823e-01 -1.21873650e+00 6.17939014e-01
-6.42422588e-01 -4.16299025e-01 -7.86703819e-01 -1.24358057e+00
4.44874275e-01 -4.30851030e-01 -9.17325632e-01 -7.53058105e-01
-1.01299996e+00 -4.14214642e-01 1.82587820e+00 -2.10552535e-01
2.06464913e-01 -1.30648658e+00 8.30463175e-01 1.36821577e-01
7.41007115e-02 -9.29753546e-01 -6.42642000e-01 -4.94151662e-02
-1.61395425e+00 9.24641894e-01 -1.80790634e+00 2.60945833e-02
2.51620478e-01 -1.37166492e+00 -5.44686268e-01 4.88666865e-01
1.04054454e+00 -4.53437729e-01 -4.76563488e-02 -5.37804304e-01
-7.80898952e-01 -2.14847616e-01 4.62686639e-01 6.81068567e-02
-1.61825081e+00 4.84324796e-02 7.45973514e-01 -5.55606619e-02
-3.45508822e-04 -2.06063368e+00 1.75935275e+00 1.08048387e+00]

outfile.seek(0) # using the same array
0

M = np.load(outfile)

M
array([ 6.78274090e-01, -8.52825948e-01, -6.03075501e-01, -1.00420005e+00,
-7.96532326e-01, -1.65382101e-01, 1.43116450e-01, -1.97848426e-01,
-1.33776608e+00, 1.23098969e+00, -5.90892251e-01, 2.25601202e-02,
8.78504619e-01, -2.12425011e-01, -5.30371020e-02, 4.95412246e-04,
5.93632659e-01, 1.57925727e+00, -1.56882239e-02, -6.29695805e-01,
1.24938150e-01, 8.80617366e-01, -7.99251066e-01, 2.38656180e+00,
3.32651204e-01, -3.57059719e-01, 1.61777246e-01, -6.87525484e-01,
8.93905681e-02, 3.62200207e-01, 4.91261620e-01, -5.67746134e-01,
1.48533911e+00, 4.29460700e-02, -5.28135571e-01, 3.09401599e-01,
1.45018211e+00, 3.16740944e-03, -8.63631498e-01, 6.35933960e-01,
-7.16705078e-01, 1.66224636e+00, 9.34081343e-01, -1.32380505e+00,
-4.16166793e-01, 1.11065891e+00, -4.16605130e-03, 2.71138500e-01,
1.22826598e-01, -4.06749298e-01, 6.62851533e-01, -7.70384316e-01,
-4.32017494e-01, -2.44006823e-01, -1.21873650e+00, 6.17939014e-01,
-6.42422588e-01, -4.16299025e-01, -7.86703819e-01, -1.24358057e+00,
4.44874275e-01, -4.30851030e-01, -9.17325632e-01, -7.53058105e-01,
-1.01299996e+00, -4.14214642e-01, 1.82587820e+00, -2.10552535e-01,
2.06464913e-01, -1.30648658e+00, 8.30463175e-01, 1.36821577e-01,
7.41007115e-02, -9.29753546e-01, -6.42642000e-01, -4.94151662e-02,
-1.61395425e+00, 9.24641894e-01, -1.80790634e+00, 2.60945833e-02,
2.51620478e-01, -1.37166492e+00, -5.44686268e-01, 4.88666865e-01,
1.04054454e+00, -4.53437729e-01, -4.76563488e-02, -5.37804304e-01,
-7.80898952e-01, -2.14847616e-01, 4.62686639e-01, 6.81068567e-02,
-1.61825081e+00, 4.84324796e-02, 7.45973514e-01, -5.55606619e-02,
-3.45508822e-04, -2.06063368e+00, 1.75935275e+00, 1.08048387e+00])

Python/sorts/random_pivot_quick_sort.py

TEST_CASES = [
{‘input’: [8, 7, 6, 5, 4, 3, -2, -5], ‘expected’: [-5, -2, 3, 4, 5, 6, 7, 8]},
{‘input’: [-5, -2, 3, 4, 5, 6, 7, 8], ‘expected’: [-5, -2, 3, 4, 5, 6, 7, 8]},
{‘input’: [5, 6, 1, 4, 0, 1, -2, -5, 3, 7], ‘expected’: [-5, -2, 0, 1, 1, 3, 4, 5, 6, 7]},
{‘input’: [2, -2], ‘expected’: [-2, 2]},
{‘input’: [1], ‘expected’: [1]},
{‘input’: [], ‘expected’: []},
]

‘’’
TODO:
- Fix some broken tests in particular cases (as [] for example),
- Unify the input format: should always be function(input_collection) (no additional args)
- Unify the output format: should always be a collection instead of
updating input elements and returning None
- Rewrite some algorithms in function format (in case there is no function definition)
‘’’

TEST_FUNCTIONS = [
bogo_sort,
bubble_sort,
bucket_sort,
cocktail_shaker_sort,
comb_sort,
counting_sort,
cycle_sort,
gnome_sort,
heap_sort,
insertion_sort,
merge_sort_fastest,
merge_sort,
pancake_sort,
quick_sort_3partition,
quick_sort,
radix_sort,
quick_sort_random,
selection_sort,
shell_sort,
tim_sort,
topological_sort,
tree_sort,
wiggle_sort,
]

for function in TEST_FUNCTIONS:
for case in TEST_CASES:
result = function(case[‘input’])
assert result == case[‘expected’], ‘Executed function: {}, {} != {}’.format(function.name, result, case[‘expected’])

Python/sorts/tim_sort.py
#list相加还是list

lst
[5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]

lst[:5]
[5, 9, 10, 3, -4]

lst[5:7]
[5, 178]

value = lst[1]
value
9

lst[:5]+lst[5:7]+[value]
[5, 9, 10, 3, -4, 5, 178, 9]

Python/sorts/topological_sort.py