[파이썬 알고리즘 인터뷰] 정렬

• 정렬 알고리즘: 목록의 요소를 특정 순서대로 넣는 알고리즘, 대게 숫자식 순서와 사전식 순서로 정렬
• 버블 정렬(O(n^2)): 배열의 요소를 끝까지 순차적으로 탐색하며 연달아 있는 2개의 요소의 순서가 맞지 않으면 스왑
• 병합 정렬(O(nlogn)): 배열을 더 이상 분할이 안될때까지 반씩 나누고, 요소들을 정렬하면서 이어붙힌다
  • 대부분의 경우 퀵 정렬보다 느리지만 일정한 속도와 안정 정렬인 점 때문에 많이 쓰인다
• 퀵 정렬(O(nlogn)): 분할 정복 알고리즘에 피벗 개념을 추가해 피벗보다 작으면 왼쪽, 크면 오른쪽에 배치되게 분할
  • 이미 정렬된 배열이 입력되는 등의 비효율적인 상황에서는 O(n^2)
  • 가장 간단한 분할 알고리즘인 로무토 파티션은 피벗이 가장 오른쪽 요소
• 안정 정렬: 입력된 순서가 다른 기준으로 재정렬했을때 유지되는 정렬 ↔ 불안정 정렬
  • 병합 정렬, 버블 정렬: 안정 정렬
  • 퀵 정렬은 불안정 정렬
• 파이썬의 기본 정렬 알고리즘은 병합 정렬과 삽입 정렬을 조합한 팀소트

148. Sort List

- 병합 정렬 -> 연결리스트이기 때문에 런너 기법을 활용해 재귀적으로 분할하고 정렬해가면서 정복

- 퀵 정렬 -> 연결리스트이기 때문에 피벗을 원하는 위치로 설정하기 어렵고, 이미 정렬된 리스트가 입력되면 계속 불균형 리스트로 분할되어 시간초과

- 내장함수 -> 연결리스트를 리스트로 바꾸고 정렬한 뒤 다시 연결리스트로 바꾼다

 

56. Merge Intervals

- 병합 가능한 요소들은 연속적으로 배치되게끔 입력값 정렬 후, 빈 리스트에 앞부터 차례로 병합된 리스트 추가 O(nlogn)

• 콤마(,) 연산자: 중첩 리스트로 만들어주는 연산자
• a와 b가 리스트일때 a += b, 와 a += [b]는 동일한 연산

147. Insertion Sort List

※ 삽입 정렬: 입력값에서 하나씩 추출해 빈 리스트에 순서에 맞게 삽입 (정렬된 리스트 값들과 차례로 스왑해 자리 찾음)

- 삽입 정렬 -> head 앞에 parent와 cur 포인터로 None 노드 생성, parent는 root 가리키고, cur는 정렬된 리스트를 탐색하며 삽입될 위치 가리킴

- 삽입 정렬의 비교 조건 개선 -> cur이 parent 위치, 즉 맨처음으로 가지 않아도 되는 상황을 배제

# 위아래 동일
cur = parent = ListNode(0)
#############################
cur = ListNode(0)
parent = cur

 

179. Largest Number

- 삽입 정렬 -> 요소 a와 b 비교할 때 a+b와 b+a 크기 비교

# 삽입정렬 수도 코드
# 배열로 구현되어 제자리 정렬 가능
# i로 탐색하면서, 인덱스 0 ~ i-1까지의 배열에 인덱스 i에 해당하는 값을 삽입하는 것으로 생각
i = 1
while i < length(a)
	j = i
    while j > 0 and a[j-1] > a[j]
    	swap a[j] and a[j-1]
        j = j-1
    end while
    i = i+1
end while

 

242. Valid Anagram

- 정렬값 비교

 

75. Sort Colors

- 네덜란드 국기 문제 응용 -> 배열을 순차적으로 탐색하면서 0은 왼쪽으로, 2는 오른쪽으로 스왑

 

973. K Closest Points to Origin

- 우선순위 큐 -> heapq 모듈로 거리정보 포함하여 힙 구성하고 k번 추출

- 내 풀이: 리스트에 가까운 순으로 정렬하고 슬라이싱하여 추출 -> 힙 사용이 훨씬 효율적