버블 정렬: Bubble Sort
O(n^2)으로, 2중 for문으로 swap해 가면서 정렬해 나가는 방법.
for i in range(len(A)):
for j in range(len(A)):
if A[j]>A[j+1]:
A[j], A[j+1] = A[j+1], A[j]병합 정렬: Merge Sort
분할 정복의 진수를 보여주는 알고리즘. 최선과 최악 모두 O(nlogn).
대부분의 경우 퀵 정렬보다 느리지만 일정한 실행 속도뿐만 아니라 무엇보다도 안정 정렬(Stable sort)이라는 점에서 여전히 상용 라이브러리에 많이 쓰이고 있음.
퀵 정렬: Quick Sort
피봇을 기준으로 좌우로 나누는 특징 때문에 파티션 교환 정렬(Partition Exchange Sort)이라고도 불리운다. 병합 정렬과 마찬가지로 분할 정복 알고리즘이며, 여기에 피벗(Pivot)이라는 개념을 통해 피벗보다 작으면 왼쪽, 크면 오른쪽과 같은 방식으로 파티셔닝하면서 쪼개 나감.
def QuickSort(A, lo, hi):
if lo < hi:
pivot = partition(A, lo, hi)
QuickSort(A, lo, pivot-1)
QuickSort(A, pivot-1, hi)로무터 파티션
항상 맨 오른쪽의 피봇을 택하는 단순한 방식.
def partition(lo, hi):
pivot = A[hi]
left = lo
for right in range(lo, hi):
# lo부터 hi 전까지 pivot보다 작은 경우: 왼쪽으로, 큰 경우: 오른쪽으로.
if A[right] < pivot:
A[left], A[right] = A[right], A[left]
left += 1
# 마지막으로 swap해 주기.
A[left], A[hi] = A[hi], A[left]
return left최악의 경우: O(n^2), 이미 정렬된 배열이 입력값으로 들어오면 가장 오른쪽에 있는, 즉 최댓값이 늘 pivot으로 선정되기 때문에.
안정 정렬 vs 불안정 정렬
예를 들어, 택배가 도착한 시각별로 정렬한 로그에서 도착지 도시를 그룹으로 묶어 정렬할 때, 그룹 내에서 도착 시각 순서대로 정렬되지 않으면 불안정 정렬, 정렬되면 안정 정렬이 된다.
퀵 소트는 불안정 정렬이다.
이 때문에 실무에서는 병합 정렬을 더 자주 사용, 파이썬의 기본 정렬 알고리즘으로는 병합 정렬과 삽입 정렬을 휴리스틱하게 조합한 팀소트를 사용한다.
문제들
리스트 정렬
연결 리스트를 O(nlogn)으로 정렬하라.
입력: 4 2 1 3
출력: 1 2 3 4
풀이1-병합 정렬
def merge(l1, l2):
# l1, l2는 노드
if l1 and l2:
# 마지막 next가 None일 수 있음.
if l1.val > l2.val:
l1, l2 = l2, l1
l1.next = self.merge(l1.next, l2)
return l1 or l2
def sortList(head):
if not (head and head.next):
return head
# 런너 기법 활용
half, slow, fast = None, head, head
while fast and fast.next:
half, slow, fast = slow, slow.next, fast.next.next
half.next = None
# 분할 재귀 호출
l1 = sortList(head)
l2 = sortList(slow)
return merge(l1, l2)풀이2-퀵 정렬
퀵 정렬은 원하는 형태로 설정하기 어려움, 이미 정렬된 상태인 경우 계속해서 불균형 리스트로 나뉨.
따라서 해당 풀이 방법에서는 퀵 정렬로 푸는 게 좋지 않음.
풀이3-내장 함수를 이용하는 실용적인 방법
내장 함수는 Timsort를 사용하기 때문에 상당히 효율적이다. 따라서 이걸 이용해서 사용한다면 상당히 좋을 것.
구간 병합
겹치는 구간을 병합하라.
입력: [[1,3],[2,6],[8,10],[15,18]]
출력: [[1,6], [8,10],[15,18]]
정렬하여 병합
def merge(intervals):
merged = []
for i in sorted(intervals, key=lambda x: x[0]):
if i[0] < merged[-1][1]:
merged[-1][1] = i[1]
else:
merged += i,
return merged삽입 정렬 리스트
연결 리스트를 삽입 정렬로 정렬하라.
삽입 정렬
head는 정렬을 해야 하는 대상, cur는 정렬을 끝낸 대상
cur = parent = ListNode(None)
while head:
while cur.next and cur.next.val < head.val:
cur = cur.next가장 큰 수
항목들을 조합하여 만들 수 있는 가장 큰 수를 출력하라.
삽입 정렬
맨 앞에서부터 자릿수 단위로 비교해서 크기 순으로 정렬한다.
삽입 정렬에서 j>0인 동안~ 같은 end point를 잘 살펴보기
class Solution:
# 문제에 적합한 비교 함수
@staticmethod
def to_swap(n1: int, n2: int) -> bool:
return str(n1) + str(n2) < str(n1) + str(n2)
# 삽입 정렬 구현
def largestNumber(self, nums: List[int]) -> str:
i = 1
while i< len(nums):
j = i
while j>0 and self.to_swap(nums[j-1], nums[j]):
nums[j], nums[j-1] = nums[j-1], nums[j]
j -= 1
i += 1
return str(int(''.join(map(str, nums))))색 정렬
빨간색을 0, 흰색을 1, 파란색을 2라고 할 때 순서대로 인접하는 제자리 정렬을 수행하라.
네덜란드 국기 문제 응용
red는 확실히 검증된 1보다 작거나 같은 값들의 마지노선blue는 확실히 검증된 1보다 큰 값들의 마지노선white는 blue까지 계속 움직이면서 1보자 작은 지 혹은 큰 지 판별하고 red 이전 혹은 blue 이후로 넣어 줌. (물론 이때 red++, blue—)- 예시
def sortColors(self, nums:List[int]) -> None:
red, white, blue = 0,0,len(nums)
while white < blue:
if nums[white] < 1:
nums[red], nums[white] = nums[white], nums[red]
white += 1
red += 1
elif nums[white] > 1:
blue -= 1
nums[white], nums[blue] = nums[blue], nums[white]
else:
white += 1원점에 k번째로 가까운 점(K closest Points to Orgin)
평면상에 points 목록이 있을 때, 원점 (0,0)에서 K번째까지 가까운 점 목록을 순서대로 출력하라. 평면상 두 점의 거리는 유클리드 거리로 한다.
- 유클리드 거리:
우선순위 큐 이용하기
가장 거리가 가까운 순서이므로, 최소힙 그대로 이용하면 됨. 이때 굳이 square root 이용할 필요 없음.
def kClosest(self, points: List[List[int]], K:int) -> List(List[int]):
heap = []; ans = []
for [x, y] in points:
dist = x ** 2 + y ** 2
heapq.heappush(heap, (dist, x, y))
for i in range(K):
dist, x, y = heapq.heappop(heap)
ans.append([x,y])
return ans