[白俊]2751号:数列2(Python)

質問する

私の答え

### sorted 사용
import sys
input=sys.stdin.readline

n=int(input())
li=[]

for i in range(n):
    li.append(int(input()))

for i in sorted(li):
    print(i)

fishen内蔵関数sortedを用いて解凍した.(sortも可能です.sortは円アレイに変更された円アレイの値には影響しません.ソート後の円アレイの値にも影響しません.)

連結ソートで展開

### 합병정렬(nlogn)
import sys
input=sys.stdin.readline

n=int(input())
li=[]

for i in range(n):
    li.append(int(input()))

def sort(arr):
    if len(arr)<2:
        return arr
    
    mid=len(arr)//2
    left=sort(arr[:mid])
    right=sort(arr[mid:])

    return merge(left,right)
    
def merge(left,right):
    new_list=[]
    i=0
    j=0
    
    while (i<len(left)) & (j<len(right)):
        if left[i]>right[j]:
            new_list.append(right[j])
            j+=1
        else:
            new_list.append(left[i])
            i+=1
    while (j<len(right)):
            new_list.append(right[j])
            j+=1
    while (i<len(left)):
            new_list.append(left[i])
            i+=1
    return new_list
    
for i in sort(li):
    print(i)

連結ソートで解くと、最初のコミットが間違っています.(jはiで書き間違えた...ははは)
合併ソートはスライス征服方式を採用し、2つの半分に並んだ後、これを基準に左揃えleft=sort(arr[:mid])、右揃えright=sort(arr[mid:])である.
次に、並べ替えをマージします.merge(left,right)右側の値が左側の値より小さい場合は、新しい配列(new list)に右側の値を追加し、数値を増やします.

if left[i]>right[j]:
	new_list.append(right[j]) 
	j+=1

左の値も同じです.

else:
	new_list.append(left[i])
    i+=1

その後、ソートを行い、残りの値を配列に追加し、配列を返します.

while (j<len(right)):
            new_list.append(right[j])
            j+=1
    while (i<len(left)):
            new_list.append(left[i])
            i+=1
    return new_list