문제 정리

<aside> 👉🏿 배열이 주어지고 이를 정렬하는 문제이다.

</aside>

접근 방법

<aside> 👉🏿 시간 복잡도 N(logN)으로 풀어야하는 문제.

따라서 퀵 정렬로는 풀 수 없고 아래 방법으로 풀 수 있다.

병합정렬
힙정렬
파이썬 내장함수. </aside>

(1) 병합 정렬

<aside> 👉🏿 병합정렬을 다시 상기시켜 보자.

먼저 받은 리스트를 전부 분할해준다.

다시 병합하면서 정렬을 해나간다.

</aside>

<aside> 👉🏿 병합 정렬 코드로 구현

</aside>

def merge(arr1, arr2):
    result = []
    # 투포인터 초깃값 설정
    i = j = 0
    # 포인터들이 리스트의 길이보다 길지 않을때 작동
    while i < len(arr1) and j < len(arr2):
        # 첫번째 리스트가 더 작을 경우 결과값에 추가, i포인터 +1
        if arr1[i] < arr2[j]:
            result.append(arr1[i])
            i += 1
        # 두번째 리스트가 더 작을 경우 결과값 추가, j포인터 +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(lst):
    # 리스트 길이가 1보다 작으면 리스트를 그대로 반환
    if len(lst) <= 1:
        return lst
    # 중간 지점 설정
    mid = len(lst) // 2
    # 중간 지점을 기준으로 좌우 나눈다.
    L = lst[:mid]
    R = lst[mid:]
    # 병합정렬
		return merge(mergesort(L), mergesort(R))

(2) Heap sort - 내장함수 사용

<aside> 👉🏿 heapq를 이용한 풀이이다.

</aside>

class Solution:
    def sortArray(self, nums):
        heap = []
        for num in nums :
            heapq.heappush(heap, num)

        list = [heapq.heappop(heap) for _ in range(len(nums))]
        return list

solution = Solution()
print(solution.sortArray([5,2,3,1]))

(3) Heap sort - 직접 구현

<aside> 👉🏿 최소힙을 직접 구현하는 것은 최대힙 구현과 크게 다르지 않다.

아래는 최소힙을 직접 구현하고 배열 정렬을 해보았다.

</aside>