사실 이 문제는 퀵정렬, 합병정렬이 아니다.
근데 왜 이런 태그를 붙여놨느냐?
내가 메모리 제한을 못보고 합병정렬로 풀었기 때문이다.
합병정렬
합병 정렬은 배열(리스트)을 크기가 1이 될 때까지 자르고, 정렬을 하며 붙여나가는 알고리즘이다.
합병정렬은 다음과 같이 구현된다.
1. 배열을 반으로 나눈다.(길이가 1이 될때까지)
2. 양 옆의 배열을 비교하며, 합병한다.
합병정렬은 어떻게 자료가 정렬되어 있던 상관없이 시간복잡도가 O(nlogn)이다.
대신 제자리 정렬이 안되고, 임시 배열이 필요하다는 단점이 있다.
하지만 연결리스트로 작성하면, 제자리 정렬도 가능하다고 한다.
아래는 합병정렬 알고리즘이다.
def msort(l):
if len(l)==1:
return l
else:
mid=len(l)//2
left=l[:mid]
right=l[mid:]
l_list=msort(left)
r_list=msort(right)
return sorting(l_list,r_list)
def sorting(l,r):
res=[]
while len(l)>0 or len(r)>0:
if len(l)>0 and len(r)>0:
if l[0]>=r[0]:
res.append(r[0])
r=r[1:]
else:
res.append(l[0])
l=l[1:]
else:
if len(l)>0:
res.append(l[0])
l=l[1:]
elif len(r)>0:
res.append(r[0])
r=r[1:]
return res
n=int(input())
li1=[]
li=[]
k=[]
for _ in range(n):
li1.append(int(input()))
for x in li1:
if x not in li:
li.append(x)
k.append([x, li1.count(x)])
res=list(msort(li))
for x in res:
for p,q in k:
if p==x:
for _ in range(q):
print(x)msort 함수를 사용해서 분할을, sorting 함수를 이용해서 합병을 했다.(함수 이름 잘못지었다 ㅋㅋ)
아무튼 저렇게 풀게되면
이렇게 된다.
아니 가장 빠른 정렬인데 안된다고? 그렇다고 다른 정렬 알고리즘을 사용하면 시간초과가 날게 분명했다.
그래서 나는 그냥 정렬 알고리즘으로 안풀었다.
import sys
input=sys.stdin.readline
n=int(input())
li=[]
for x in range(10001):
li.append([x,0])
for _ in range(n):
k=int(input().rstrip())
li[k][1]+=1
for x,y in li:
if y>=1:
for _ in range(y):
print(x)다음은 합병정렬 사용한 김에 작성해보는 퀵정렬이다.
퀵정렬
퀵정렬은 상황에 따라 시간복잡도가 다른게 특징이다.
대부분은 존내 빠르다. O(nlog2n)
그러나 역으로 정렬되어 있는경우에는 O(n^2)의 시간복잡도를 가진다.
대부분 프로그래밍 언어의 sort()함수는 퀵함수 메커니즘에 의해 구현됐다고 한다.
퀵정렬은 다음과 같이 구현된다.
1. 배열의 임의의 값 pivot을 설정한다.
2. pivot 왼쪽과 오른쪽으로 나누어, pivot보다 작은 값, pivot보다 큰 값으로 분류한다.
3. 왼쪽과 오른쪽 배열에서 pivot을 다시 설정하여 반복한다.
4. 배열 길이가 1일때까지 반복한다.
파이썬 코드는 다음과 같다.
def qsort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left, mid, right = [], [], []
for num in arr:
if num < pivot:
left.append(num)
elif num > pivot:
right.append(num)
else:
mid.append(num)
return qsort(lesser_arr) + equal_arr + qsort(greater_arr)
