アルゴリズム: Merge Sort & Quick Sort

Merge Sort 概要

• arrayを二分していって値の比較をしていくSortアルゴリズム
• 計算量は O(N log(N)).

詳細

www.youtube.com

サンプル問題

Kth Largest Element in an Array - LeetCode

サンプルコード

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:

        def merge_sort(array):
            if len(array) <= 1:
                return

            mid = len(array)//2
            left = array[:mid]
            right = array[mid:]

            merge_sort(left)
            merge_sort(right)

            merge_two_sorted_list(left, right, array)

        def merge_two_sorted_list(left, right, array):
            leftLen = len(left)
            rightLen = len(right)
            i = j = k = 0

            while i < leftLen and j < rightLen:
                if left[i] <= right[j]:
                    array[k] = left[i]
                    i += 1
                else:
                    array[k] = right[j]
                    j += 1
                k += 1
            while i < leftLen:
                array[k] = left[i]
                i += 1
                k += 1
            while j < rightLen:
                array[k] = right[j]
                j += 1
                k += 1

        merge_sort(nums)

        return nums[len(nums)-k]

Quick Sort 概要

• pivotといわれる指標みたいなものを選んで、それと値を比較していく.
• pivotより左のパーティション、右のパーティションを作成し、それぞれの値はpivotよりも小さく、大きくなるようにsortしていく.
• 計算量は O(N logN)だが、最悪 O(N²)になってしまう場合もある.

詳細

www.youtube.com

サンプル

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:

        def partition(nums, start, end):
            pivot_idx = start
            pivot = nums[pivot_idx]

            while start < end:
                # 現在の値がpivotを超えるまでstart idxをインクリメント
                while start < len(nums) and nums[start] <= pivot:
                    start += 1
                
                # 現在の値がpivotより小さくなるまでend idxをデクリメント
                while nums[end] > pivot:
                    end -= 1
                
                # start idxがend idxより小さい場合は値をswap
                if start < end:
                    nums[start], nums[end] = nums[end], nums[start]

            # endがstartより小さくなった場合、end idxの値とpivot値をswap
            nums[pivot_idx], nums[end] = nums[end], nums[pivot_idx]

            return end

        def quick_sort(array, start, end):
            if start < end:
                partition_idx = partition(array, start, end)
                quick_sort(array, start, partition_idx-1)
                quick_sort(array, partition_idx+1, end)

        quick_sort(nums, 0, len(nums)-1)

        return nums[len(nums)-k]