合并排序实施检查 [英] Merge Sort Implementation Check
问题描述
我怀疑是我实现合并排序了两种情况下具体的：
1.如果列表的大小为2，那么我已经换了值，如果他们不是升序排列别的我已经回到他们进来。
2.在当列表试图检查它的元素数以外的合并功能，我已经分配了最大数量的（9999），以便在情况相比与它总是假的。
谁能告诉我，如果我的合并排序的执行是否正确？由于在排序完成，但合并执行某种确切的或者是错误的，因为案件？
这是我的code：
#unsorted LIST
u_list = [3,6,8,1,4,7,2,12,45];
未排序列表#Size
global_size = LEN（u_list）
高清FOO（temp_list）：
size_of_list = LEN（temp_list）
的#if列表的大小是1
如果size_of_list == 1：
返回temp_list
的#if列表的大小是2
如果size_of_list == 2：
如果temp_list [0]≥ temp_list [1]：
temp_list [0]，temp_list [1] = temp_list [1]，temp_list [0]
返回temp_list
其他：
返回temp_list
的#if列表的大小大于2
如果size_of_list＆GT; 2：
数= 1
I = 0
如果size_of_list％2 == 0：
MID1 = size_of_list / 2
其他：
MID1 =（size_of_list / 2）+1
MID2 = size_of_list - MID1
newlist1 =名单（）
newlist2 =名单（）
为电子商务在temp_list：
如果计数＆GT; = MID1 + 1：
newlist2.append（五）
其他：
newlist1.append（五）
如果count == size_of_list：
打破
数=计数+ 1
sorted_list =名单（）
回合并（FOO（newlist1），富（newlist2））
#Merging所有排序组件
DEF合并（List1中，list2中）：
I = 0
J = 0
K = 0
size_of_list = LEN（List1中）+ LEN（list2中）
sorted_list =名单（）
而K＆LT; = size_of_list - 1：
如果我== LEN（List1中）：
list1.append（9999）
在j == LEN（list2中）：
list2.append（9999）
如果List1的[1] - ; list2中[J]：
sorted_list.append（List1的[I]）
I = I + 1
ELIF list2中[J] LT; List1的[我]：
sorted_list.append（list2中[J]。）
当J = J + 1个
K = K + 1
回报sorted_list
打印FOO（u_list）
说实话，我感到非常不安，如果我看到code这样的）。这可能是正确的，但我的胆量感觉最高审计机关它不是（如果有号码> 9999？）。它比必要更复杂。语法是Python的，但你不使用Python的力量。
下面就是我将在Python中实现合并排序：
高清merge_sort（李）：
如果len（LI）LT; 2：回力
M = len个（LI）/ 2
回合并（merge_sort（李[：M]），merge_sort（李[M：]））
高清合并（L，R）：
结果= []
I = J = 0
而I＆LT;的len（升）和j＆其中;的len（r）的：
如果升[1] - ; - [R [J]：
result.append（L [I]）
I + = 1
其他：
result.append（R [J]。）
J + 1 =
结果+ = L [I：]
结果+ = R [J：]
返回结果
I am doubtful of my implementation of the merge sort for two cases specifically:
1. If the size of the list is 2 , then i have swapped the values if they are not in the ascending order else i have returned them.
2. In the merge function when the list tries to check outside the number of elements in it , I have assigned the greatest number(9999), so that in case of comparison with it always comes false.
Can anyone tell me if the implementation of my merge sort is correct or not? As in sorting is complete, but is the implementation of merge sort exact or is it wrong because of the cases?
Here is my code :
#unsorted LIST
u_list = [3,6,8,1,4,7,2,12,45];
#Size of the unsorted list
global_size=len(u_list)
def foo(temp_list):
size_of_list =len(temp_list)
#If the size of the list is 1
if size_of_list == 1:
return temp_list
#If the size of the list is 2
if size_of_list == 2:
if temp_list[0] > temp_list[1]:
temp_list[0],temp_list[1] = temp_list[1],temp_list[0]
return temp_list
else:
return temp_list
#If the size of the list is greater than 2
if size_of_list > 2:
count = 1
i = 0
if size_of_list % 2 == 0:
mid1 = size_of_list/2
else:
mid1 = (size_of_list/2) + 1
mid2 = size_of_list - mid1
newlist1 = list()
newlist2 = list()
for e in temp_list:
if count >= mid1 + 1:
newlist2.append(e)
else:
newlist1.append(e)
if count == size_of_list:
break
count = count + 1
sorted_list = list()
return merge (foo(newlist1),foo(newlist2))
#Merging all the sorted components
def merge(list1,list2):
i = 0
j = 0
k = 0
size_of_list = len(list1) + len(list2)
sorted_list = list()
while k <= size_of_list - 1 :
if i == len(list1):
list1.append(9999)
if j == len(list2):
list2.append(9999)
if list1[i] < list2[j]:
sorted_list.append(list1[i])
i = i + 1
elif list2[j] < list1[i]:
sorted_list.append(list2[j])
j = j + 1
k = k + 1
return sorted_list
print foo(u_list)
To be honest, I feel very uneasy if I see code like this ;). It may be correct, but my guts feeling sais it's not (what if there are numbers > 9999?). It is more complicated than necessary. The syntax is Python, but you are not using the power of Python.
Here's how I would implement merge sort in Python:
def merge_sort(li):
if len(li) < 2: return li
m = len(li) / 2
return merge(merge_sort(li[:m]), merge_sort(li[m:]))
def merge(l, r):
result = []
i = j = 0
while i < len(l) and j < len(r):
if l[i] < r[j]:
result.append(l[i])
i += 1
else:
result.append(r[j])
j += 1
result += l[i:]
result += r[j:]
return result
这篇关于合并排序实施检查的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
