<aside> 👉🏿 문제 링크

</aside>

문제 정리

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

파이썬 내장함수를 써서는 안된다.

</aside>

접근 방법

<aside> 👉🏿 상당히 많은 방법으로 풀어 볼 수 있다.

복습 차원에서 제공한 문제인 것 같다.

</aside>

코드 진행

<aside> 👉🏿 총 3가지 방법으로 진행했다.

• Quick Sort
• Merge Sort
• Heap Sort </aside>

class BinaryMinHeap:
    def __init__(self):
        self.items = [None]

    def __len__(self):
        return len(self.items) - 1

    def _percolate_up(self):
        cur = len(self)
        parent = cur // 2

        while parent > 0:
            if self.items[cur] < self.items[parent]:
                self.items[cur], self.items[parent] = self.items[parent], self.items[cur]

            cur = parent
            parent = cur // 2

    def _percolate_down(self, cur):
        smallest = cur
        left = 2 * cur
        right = 2 * cur + 1

        if left <= len(self) and self.items[left] < self.items[smallest]:
            smallest = left

        if right <= len(self) and self.items[right] < self.items[smallest]:
            smallest = right

        if smallest != cur:
            self.items[cur], self.items[smallest] = self.items[smallest], self.items[cur]
            self._percolate_down(smallest)

    def insert(self, k):
        self.items.append(k)
        self._percolate_up()

    def extract(self):
        if len(self) < 1:
            return None
        root = self.items[1]
        self.items[1] = self.items[-1]
        self.items.pop()
        self._percolate_down(1)

        return root

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

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

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

    def merge_sort(self, nums):
        if len(nums) <= 1:
            return nums

        mid = len(nums) // 2
        L = nums[:mid]
        R = nums[mid:]
        return self.merge(self.merge_sort(L), self.merge_sort(R))

    def quick_sort(self, list, start, end):
        def partition(part, ps, pe):
            pivot = part[pe]
            i = ps - 1
            for j in range(ps, pe):
                if part[j] < pivot:
                    i += 1
                    part[j], part[i] = part[i], part[j]

            part[i + 1], part[pe] = part[pe], part[i + 1]
            return i + 1

        if start >= end:
            return None

        p = partition(list, start, end)
        self.quick_sort(list, start, p - 1)
        self.quick_sort(list, p + 1, end)
        return list

    def sortColors(self, nums):
        # nums[:] = self.merge_sort(nums)
        # nums[:] = self.quick_sort(nums, 0, len(nums) - 1)
        heap = BinaryMinHeap()
        for num in nums:
            heap.insert(num)

        nums[:] = [heap.extract() for _ in range(len(nums))]
        print(nums)

solution = Solution()
solution.sortColors(nums=[0,1,2])