I am an amazing person.

1 분 소요

2751번 : 수 정렬하기 2

2751: 수 정렬하기 2

방법 1 (틀림)

  • QuickSort
import sys
input = sys.stdin.readline


def quicksort(arr):
    def sort(l, r):
        if l >= r:
            return

        mid = partition(arr, l, r)
        sort(l, mid-1)
        sort(mid, r)

    def partition(arr, l, r):
        pivot = arr[(l+r)//2]
        while l <= r:
            while arr[l] < pivot:
                l += 1
            while arr[r] > pivot:
                r -= 1
            if l <= r:
                arr[l], arr[r] = arr[r], arr[l]
                l += 1
                r -= 1
        return l

    return sort(0, len(arr)-1)



if __name__ == '__main__':
    n = int(input())
    arr = []

    for _ in range(n):
        arr.append(int(input()))

    quicksort(arr)
    for num in arr:
        print(num)

방법 2 (옳은 풀이)

  • MergeSort
import sys
input = sys.stdin.readline

def merge(arr1, arr2):
    i, j = 0, 0
    result = []
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1

    while i < len(arr1):
        result.append(arr1[i])
        i += 1

    while j < len(arr2):
        result.append(arr2[j])
        j += 1

    return result

def mergesort(arr):
    # 더 이상 쪼갤 수 없는 경우
    if len(arr) <= 1:
        return arr

    # list 반으로 쪼개기
    mid = len(arr)//2

    return merge(mergesort(arr[:mid]), mergesort(arr[mid:]))


if __name__ == '__main__':
    n = int(input())
    arr = []

    for _ in range(n):
        arr.append(int(input()))

    arr = mergesort(arr)
    for num in arr:
        print(num)

분석

QuickSort 는 안되고 MergeSort는 되는 이유

QuickSort

  • 평균 시간 복잡도: O(NlogN)
  • ⭐최악의 경우 O(N^2)⭐
    • 이미 정렬 or 역정렬된 경우, 매우 느림
    • pivot 선정 기준 또한 성능에 영향을 줌
      • 정말 잘 구현하지 않는한, 여전히 효율이 좋지 않으므로 알고리즘 문제에서 QuickSort는 비추천

MergeSort

  • 평균 시간 복잡도: O(NlogN)
  • 최악의 경우에도 O(NlogN)

다른 정렬들은?

  • HeapSort: O(NlogN)
  • Bubble / Selection / Insertion: O(N^2)

자료 출처

참고