https://www.acmicpc.net/problem/2751
주어진 숫자를 오름차순으로 정렬하는 문제다.
n이 1,000,000
개이므로 삽입 정렬, 버블 정렬은 사용할 수 없다.
O(n log n)
인 정렬들을 찾아보았다.
import sys
n=int(sys.stdin.readline().rstrip())
unsorted_list=[]
sorted_list=[]
# [divide]
# 리스트 요소가 1개가 될때까지 나눔 / 왼쪽,오른쪽 merge
def merge_sort(list):
if len(list) <= 1:
return list
mid = len(list) // 2
leftList = list[:mid]
rightList = list[mid:]
leftList = merge_sort(leftList)
rightList = merge_sort(rightList)
return merge(leftList, rightList)
# [merge]
#1. 분리한 왼쪽리스트, 오른쪽 리스트의 각각 첫번째 요소를 비교해 더 작은 값을 결과 리스트에 저장
#2. 저장한 값은 리스트에서 지움.
#3. 두 리스트 모두 요소가 하나도 안남을 때까지 반복
def merge(left, right):
merged_list = []
l=h=0
while l < len(left) and h < len(right):
if (left[l] < right[h]):
merged_list.append(left[l])
l+=1
else:
merged_list.append(right[h])
h+=1
merged_list += left[l:]
merged_list += right[h:]
return merged_list
for i in range(n):
num=int(sys.stdin.readline())
unsorted_list.append(num)
sorted_list=merge_sort(unsorted_list)
for i in sorted_list:
print(i)
힙 정렬은 마지막 레벨을 제외한 모든 레벨이 꽉 채워진 완전이진트리를 기본으로 한다.
완전이진트리를 1차열 배열로 표현하면 인덱스가 k인 노드의 왼쪽 자식 인덱스는 2k+1, 오른쪽 자식 인덱스는 2k+2
즉, 루트가 왼쪽 노드나 오른쪽 노드보다 작으면 위치를 바꿔준다.
import sys
n=int(sys.stdin.readline().rstrip())
unsorted_list=[]
sorted_list=[]
def heapify(unsorted, index, heap_size):
largest = index
left_index = 2 * index + 1
right_index = 2 * index + 2
if left_index < heap_size and unsorted[left_index] > unsorted[largest]:
largest = left_index
if right_index < heap_size and unsorted[right_index] > unsorted[largest]:
largest = right_index
if largest != index:
unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
heapify(unsorted, largest, heap_size)
def heap_sort(unsorted):
n = len(unsorted)
# BUILD-MAX-HEAP (A) : 위의 1단계
# 인덱스 : (n을 2로 나눈 몫-1)~0
# 최초 힙 구성시 배열의 중간부터 시작하면
# 이진트리 성질에 의해 모든 요소값을
# 서로 한번씩 비교할 수 있게 됨 : O(n)
for i in range(n // 2 - 1, -1, -1):
heapify(unsorted, i, n)
# Recurrent (B) : 2~4단계
# 한번 힙이 구성되면 개별 노드는
# 최악의 경우에도 트리의 높이(logn)
# 만큼의 자리 이동을 하게 됨
# 이런 노드들이 n개 있으므로 : O(nlogn)
for i in range(n - 1, 0, -1):
unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
heapify(unsorted, 0, i)
return unsorted
for i in range(n):
num=int(sys.stdin.readline())
unsorted_list.append(num)
sorted_list=heap_sort(unsorted_list)
for i in sorted_list:
print(i)
피봇을 기준으로 피봇보다 작은 값은 왼쪽에, 큰 값은 오른쪽으로 몰아서 정렬한다.
이렇게 정렬하면 왼쪽과 오른쪽 간 비교를 할 필요가 없어진다.
단 이 문제같은 경우는 퀵 정렬을 사용할 시 메모리 초과, 시간 초과가 발생한다.
어떤 선생님께서 아주 친절하게 설명해주신 글이 있다.
🔗 https://www.acmicpc.net/board/view/31887
퀵 정렬은 최악의 경우 O(N^2)입니다.
이름에 quick이 있다고 속으면 안 됩니다.평균 시간복잡도는 O(NlogN)이지만, 평범하게 구현한 퀵 정렬은 매우 단순한 방법으로 최악의 케이스의 시간복잡도인 O(N^2)을 만들 수 있습니다.
단순히 이미 정렬이나 역정렬된 상태로만 입력이 주어져도 퀵 정렬이 감당할 수 없습니다.
이를 회피하는 방법으로 피벗으로 중앙값의 중앙값 고르기, 재귀가 깊어지면 다른 정렬을 사용하기, 랜덤으로 섞은 뒤에 수행하기 등이 있지만 정말 잘 구현하지 않으면 여전히 효율이 매우 안 좋습니다.
그래서 퀵 정렬은 그냥 이 문제에 사용하지 않기를 권장합니다. 이 문제 뿐만 아니라 어떤 알고리즘 문제에도 사용하지 않는 것이 좋습니다.
연습하기 위한 목적으로만 쓰세요.
퀵 정렬은 어떤 문제에도 사용하지 않는 것이 좋다.. 확인..