Python unit 09をすべて統合
17310 ワード
簡単に説明するマージソートアルゴリズム
降順
#쉽게 설명한 병합 정렬 알고리즘
#입력:리스트a
#출력:정렬된 새리스트
def merge_sort(a):
n=len(a)
#종료조건:정렬할 리스트 자료개수가 한개 이하이면 정렬할 필요없음
if n<=1:
return a
#그룹을 나누어 각각 병합정렬을 호출하는 과정
mid=n//2 #중간을 기준으로 두 그룹으로 나뭄
g1=merge_sort(a[:mid])
print (g1) #재귀호출로 첫번째 그룹을 정렬
g2=merge_sort(a[mid:]) #재귀호출로 두번째 그룹을 정렬
print(g2)
# 두그룹을 하나로 병합
result=[] #두그룹을 합쳐 만들 최종결과
while g1 and g2: #두그룹에 모두 자료가 남아있는 동안 반복
if g1[0] > g2[0]:
result.append(g1.pop(0))
else:
#g2값이 더 작으면 그 값을 뺴내어 결과로 추가
result.append(g2.pop(0))
#아직 남아있는 자료들을 결과에 추가
#g1 g2중 이미 빈것은 while을 바로 지나감
while g1:
result.append(g1.pop(0))
while g2:
result.append(g2.pop(0))
return result
d=[6,8,3,9,10,1,2,4,7,5]
print(merge_sort(d))
昇順
#쉽게 설명한 병합 정렬 알고리즘
#입력:리스트a
#출력:정렬된 새리스트
def merge_sort(a):
n=len(a)
#종료조건:정렬할 리스트 자료개수가 한개 이하이면 정렬할 필요없음
if n<=1:
return a
#그룹을 나누어 각각 병합정렬을 호출하는 과정
mid=n//2 #중간을 기준으로 두 그룹으로 나뭄
g1=merge_sort(a[:mid])
print (g1) #재귀호출로 첫번째 그룹을 정렬
g2=merge_sort(a[mid:]) #재귀호출로 두번째 그룹을 정렬
print(g2)
# 두그룹을 하나로 병합
result=[] #두그룹을 합쳐 만들 최종결과
while g1 and g2: #두그룹에 모두 자료가 남아있는 동안 반복
if g1[0] <g2[0]:
result.append(g1.pop(0))
else:
#g2값이 더 작으면 그 값을 뺴내어 결과로 추가
result.append(g2.pop(0))
#아직 남아있는 자료들을 결과에 추가
#g1 g2중 이미 빈것은 while을 바로 지나감
while g1:
result.append(g1.pop(0))
while g2:
result.append(g2.pop(0))
return result
d=[6,8,3,9,10,1,2,4,7,5]
print(merge_sort(d))
一般的な連結ソート
#병합정렬
#입력 리스트a
#출력:없음(입력으로 주어진 a가 정렬됨)
def merge_sort(a):
n=len(a)
#종료조건: 정렬할 리스트의 자료 개수가 한개 이하이면 정렬할 필요가 없음
if n<=1:
return
#그룹을 나누어 각각 병합 정렬을 호출하는 과정
mid=n//2 #중간을 기준으로 두그룹으로 나눔
g1=a[:mid]
g2=a[mid:]
merge_sort(g1)
merge_sort(g2)
#두그룹을 하나로 병합
i1=0
i2=0
ia=0
while i1<len(g1) and i2<len(g2):
if g1[i1]<g2[i2]:
a[ia]<a[i2]
i1 += 1
ia += 1
print(a)
else:
a[ia]=g2[i2]
i2 += 1
ia += 1
print(a)
#아직 남아있는 자료들을 추가
while i1<len(g1):
a[ia]=g1[i1]
i1 +=1
ia +=1
while i2<len(g2):
a[ia]=g2[i2]
i2 += 1
ia += 1
d=[6,8,3,9,10,2,4,7,5]
merge_sort(d)
print(d)
Reference
この問題について(Python unit 09をすべて統合), 我々は、より多くの情報をここで見つけました https://velog.io/@jsk2342/모두의-파이썬-unit09-병합정렬テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol