Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit3c40fda

Browse files
liuzhen153poyea
authored andcommitted
More elegant coding for merge_sort_fastest (TheAlgorithms#804)
* More elegant coding for merge_sort_fastest* More elegant coding for merge_sort
1 parent70bb6b2 commit3c40fda

File tree

2 files changed

+55
-44
lines changed

2 files changed

+55
-44
lines changed

‎sorts/merge_sort.py

Lines changed: 15 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -29,36 +29,20 @@ def merge_sort(collection):
2929
>>> merge_sort([-2, -5, -45])
3030
[-45, -5, -2]
3131
"""
32-
length=len(collection)
33-
iflength>1:
34-
midpoint=length//2
35-
left_half=merge_sort(collection[:midpoint])
36-
right_half=merge_sort(collection[midpoint:])
37-
i=0
38-
j=0
39-
k=0
40-
left_length=len(left_half)
41-
right_length=len(right_half)
42-
whilei<left_lengthandj<right_length:
43-
ifleft_half[i]<right_half[j]:
44-
collection[k]=left_half[i]
45-
i+=1
46-
else:
47-
collection[k]=right_half[j]
48-
j+=1
49-
k+=1
50-
51-
whilei<left_length:
52-
collection[k]=left_half[i]
53-
i+=1
54-
k+=1
55-
56-
whilej<right_length:
57-
collection[k]=right_half[j]
58-
j+=1
59-
k+=1
60-
61-
returncollection
32+
defmerge(left,right):
33+
'''merge left and right
34+
:param left: left collection
35+
:param right: right collection
36+
:return: merge result
37+
'''
38+
result= []
39+
whileleftandright:
40+
result.append(left.pop(0)ifleft[0]<=right[0]elseright.pop(0))
41+
returnresult+left+right
42+
iflen(collection)<=1:
43+
returncollection
44+
mid=len(collection)//2
45+
returnmerge(merge_sort(collection[:mid]),merge_sort(collection[mid:]))
6246

6347

6448
if__name__=='__main__':
@@ -69,4 +53,4 @@ def merge_sort(collection):
6953

7054
user_input=raw_input('Enter numbers separated by a comma:\n').strip()
7155
unsorted= [int(item)foriteminuser_input.split(',')]
72-
print(merge_sort(unsorted))
56+
print(*merge_sort(unsorted),sep=',')

‎sorts/merge_sort_fastest.py

Lines changed: 40 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,46 @@
11
'''
2-
Python implementation of merge sort algorithm.
2+
Python implementation ofthe fastestmerge sort algorithm.
33
Takes an average of 0.6 microseconds to sort a list of length 1000 items.
44
Best Case Scenario : O(n)
55
Worst Case Scenario : O(n)
66
'''
7-
defmerge_sort(LIST):
8-
start= []
9-
end= []
10-
whilelen(LIST)>1:
11-
a=min(LIST)
12-
b=max(LIST)
13-
start.append(a)
14-
end.append(b)
15-
LIST.remove(a)
16-
LIST.remove(b)
17-
ifLIST:start.append(LIST[0])
7+
from __future__importprint_function
8+
9+
10+
defmerge_sort(collection):
11+
"""Pure implementation of the fastest merge sort algorithm in Python
12+
13+
:param collection: some mutable ordered collection with heterogeneous
14+
comparable items inside
15+
:return: a collection ordered by ascending
16+
17+
Examples:
18+
>>> merge_sort([0, 5, 3, 2, 2])
19+
[0, 2, 2, 3, 5]
20+
21+
>>> merge_sort([])
22+
[]
23+
24+
>>> merge_sort([-2, -5, -45])
25+
[-45, -5, -2]
26+
"""
27+
start,end= [], []
28+
whilelen(collection)>1:
29+
min_one,max_one=min(collection),max(collection)
30+
start.append(min_one)
31+
end.append(max_one)
32+
collection.remove(min_one)
33+
collection.remove(max_one)
1834
end.reverse()
19-
return (start+end)
35+
returnstart+collection+end
36+
37+
38+
if__name__=='__main__':
39+
try:
40+
raw_input# Python 2
41+
exceptNameError:
42+
raw_input=input# Python 3
43+
44+
user_input=raw_input('Enter numbers separated by a comma:\n').strip()
45+
unsorted= [int(item)foriteminuser_input.split(',')]
46+
print(*merge_sort(unsorted),sep=',')

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp