[ BOJ 2751 ] 수 정렬하기2(Python)

문제

https://www.acmicpc.net/problem/2751

주어진 숫자를 오름차순으로 정렬하는 문제다.

문제 풀이

n이 1,000,000 개이므로 삽입 정렬, 버블 정렬은 사용할 수 없다.
O(n log n) 인 정렬들을 찾아보았다.

[병합 정렬] (🔗 참고)

1. 리스트 요소가 1개가 될때까지 나눈다.
2. 분리한 왼쪽리스트, 오른쪽 리스트의 각각 첫번째 요소를 비교해 더 작은 값을 결과 리스트에 저장한다.
3. 저장한 값은 리스트에서 지운다.
4. 두 리스트 모두 요소가 하나도 안남을 때까지 반복한다.

[병합 정렬 코드]

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

1. 주어진 원소로 최대 힙 구성
2. 최대 힙의 루트노드 (배열 첫번째 요소) 와 말단노드 (배열 마지막 요소) 교환
3. 새 루트 노드에 대해 최대 힙 구성
4. 원소의 개수만큼 2번,3번 반복

즉, 루트가 왼쪽 노드나 오른쪽 노드보다 작으면 위치를 바꿔준다.

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)

퀵 정렬

피봇을 기준으로 피봇보다 작은 값은 왼쪽에, 큰 값은 오른쪽으로 몰아서 정렬한다.
이렇게 정렬하면 왼쪽과 오른쪽 간 비교를 할 필요가 없어진다.

• 파이썬의 list.sort()는 퀵정렬을 기본으로 한다.

단 이 문제같은 경우는 퀵 정렬을 사용할 시 메모리 초과, 시간 초과가 발생한다.

어떤 선생님께서 아주 친절하게 설명해주신 글이 있다.
🔗 https://www.acmicpc.net/board/view/31887

퀵 정렬은 최악의 경우 O(N^2)입니다.
이름에 quick이 있다고 속으면 안 됩니다.

평균 시간복잡도는 O(NlogN)이지만, 평범하게 구현한 퀵 정렬은 매우 단순한 방법으로 최악의 케이스의 시간복잡도인 O(N^2)을 만들 수 있습니다.

단순히 이미 정렬이나 역정렬된 상태로만 입력이 주어져도 퀵 정렬이 감당할 수 없습니다.

이를 회피하는 방법으로 피벗으로 중앙값의 중앙값 고르기, 재귀가 깊어지면 다른 정렬을 사용하기, 랜덤으로 섞은 뒤에 수행하기 등이 있지만 정말 잘 구현하지 않으면 여전히 효율이 매우 안 좋습니다.

그래서 퀵 정렬은 그냥 이 문제에 사용하지 않기를 권장합니다. 이 문제 뿐만 아니라 어떤 알고리즘 문제에도 사용하지 않는 것이 좋습니다.
연습하기 위한 목적으로만 쓰세요.

퀵 정렬은 어떤 문제에도 사용하지 않는 것이 좋다.. 확인..