### 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)
파이썬 내장함수인 sorted를 사용해서 풀어주었다.(sort도 가능하다. sort는 원 배열까지 수정, sorted는 원배열 값에 영향을 끼치지 않는다.)
### 합병정렬(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로 잘못썼다..ㅎ)
합병정렬은 분할 정복 방식으로, 배열을 반으로 나눈 후 이를 기준으로 왼쪽을 정렬 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