수 정렬하기2

백준 2751 : 문제링크

• 문제유형 : 정렬

• 설명

  • 데이터의 개수가 1000000개

  • NlogN의 정렬 알고리즘을 이용해야한다. -> 병합, 퀵, 힙 정렬

  • 기본 정렬 알고리즘으로 해결가능

• 풀이

  • 병합 정렬

    def merge_sort(array):
        if len(array) <= 1:
            return array
        mid = len(array) // 2
        left = merge_sort(array[:mid])
        right = merge_sort(array[mid:])
        i, j, k = 0, 0, 0
        while i < len(left) and j < len(right):
            if left[i] < left[j]:
                array[k] = left[i]
                i + = 1
            else:
                array[k] = right[j]
                j += 1
            k += 1
        if i == len(left):
            while j < len(right):
                array[k] = right[j]
                j += 1
                k += 1
        elif j == len(right):
            while i < len(left):
                array[k] = left[i]
                i += 1
                k += 1
        return array
    
    n = int(input())
    array = []
    
    for _ in range(n):
        array.append(int(input()))
    
    array = merge_sort(array)
    
    for data in array:
        print(data)

  • 정렬 라이브러리

    n = int(input())
    array = []
    
    for _ in range(n):
        array.append(int(input()))
    
    array = sorted(array)