hyunkookim 님의 블로그

75. Sort Colors  class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ # We will use the integers 0, 1, and 2 rgb = [0, 0, 0] for n in nums: rgb[n] += 1 i = 0 for n in range(len(rgb)): for _ in range(rgb[n]): nums[i] = n ..

Sorting: Bucket Sort  https://youtu.be/mMELgqz7Wnk https://youtu.be/gFesW458zsU def bucketSort(arr): # Assuming arr only contains 0, 1 or 2 counts = [0, 0, 0] # Count the quantity of each val in arr for n in arr: counts[n] += 1 # Fill each bucket in the original array i = 0 for n in range(len(counts)): for j in range(counts[n]): arr[i] = n ..

Sorting: Quick Sort  https://youtu.be/QaFmEzMtYu8 https://youtu.be/OYnYbSC-Y_w # Implementation of QuickSortdef quickSort(arr: list[int], s: int, e: int) -> list[int]: if e - s + 1 # Definition for a pair.# class Pair:# def __init__(self, key: int, value: str):# self.key = key# self.value = valueclass Solution: def quickSort(self, pairs: List[Pair]) -> List[Pair]: ..

Sorting: Merge Sort   # Implementation of MergeSortdef mergeSort(arr, s, e): if e - s + 1  1. Split Processhttps://youtu.be/dsIzDKUY-uU 2. mergeSort() using Recursive Callhttps://youtu.be/qsChtOXqO1U 3. merge() using Three Pointershttps://youtu.be/RXbe0JWUKao StableTime: O(n log n)Space: O(n)

Sorting: Insertion Sort  https://youtu.be/bPlYH--OYNc def insertionSort(arr): # Traverse through 1 to len(arr) for i in range(1, len(arr)): j = i - 1 while j >= 0 and arr[j + 1]  Stableity: Stable 안정Time Complexity:Best: O(n)Worst: O(n^2)Average: O(n^2)Space Complexity: O(1)