-
Notifications
You must be signed in to change notification settings - Fork 0
Erica Gong edited this page Feb 9, 2023
·
1 revision
- 정렬: 데이터를 특정 기준에 따라 순서대로 나열
- 정렬 라이브러리로 풀 수 있는 문제: 정렬 함수를 만들 수 있는지? 간단한 문제
- 정렬 알고리즘의 원리에 대해 물어보는 문제: 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제 풀이 가능
- 더 빠른 정렬이 필요한 문제: O(nlogn)의 정렬 알고리즘으로는 풀 수 없는 문제로 계수 정렬을 사용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 요구하는 경우가 존재.
- 단순 정렬해야 하는 경우는 정렬 라이브러리인 sorted()를 사용하고, 데이터 범위가 한정된 조건 하에, 더 빠르게 동작해야하는 경우 계수 정렬을 사용하는 것이 좋음.
파이썬 기본 정렬 라이브러리인 sorted(리스트/딕셔너리/집합) 사용하면 정렬된 결과를 반환함. 어떤 자료형을 넣든 리스트 형태로 반환함. 파이썬 sorted()는 병합 정렬 O(nlogn)을 기반으로 구현되어 있음. 따라서 일반적인 경우, 퀵 정렬보다 살짝 느리지만 최악의 경우에도 O(nlogn) 보장함.
- arr.sort()는 반환된 결과를 반환하지 않고 기존 arr를 정렬함.
- sorted(arr)는 정렬된 결과를 반환함.
- 따라서 리스트.sort()는 원본 배열을 변환해도 되는 경우에 사용하고, 원본 배열을 변환하면 안되는 경우에는 sorted(리스트)를 사용하는 것이 좋음.
- 두 메소드 모두 key= 정렬함수 를 부여해 원하는 방식으로 정렬 기준을 제공할 수 있음.
정렬의 종류에 따라 시간 복잡도 상이함. - O(n^2): 선택 정렬, 삽입 정렬, ... - O(nlogn): 퀵 정렬, 병합 정렬, ... - O(n+k): 계수 정렬, ...
- 선택 정렬: 리스트에서 가장 작은 데이터를 찾아 맨 앞에 있는 데이터와 위치를 바꾸는 과정을 (n-1)번 반복하는 알고리즘
arr = [1, 0, 3, 4, 5, 9, 6, 8, 2, 7]
# 선택 정렬 구현 코드
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[min_idx] > arr[j]:
min_idx = i
arr[i], arr[min_idx] = arr[min_idx], arr[i]
print(arr)- O(n^2) 시간복잡도
- 비교 연산 수: n-1 + n-2 + n-3 + ... + 3 + 2 + 1 = n(n+1)/2
- 삽입 정렬: 리스트에서 데이터를 하나하나 확인하며 적절한 위치에 삽입해 정렬하는 방법
- 특정 데이터 앞까지는 이미 정렬된 상태로 가정. (두번째 데이터부터 시작. 데이터 하나는 이미 정렬되어 있다고 가정하므로.)
- 이미 정렬된 리스트에 특정 데이터가 들어갈 위치를 파악하고 해당 위치에 삽입하는 과정을 (n-1)번 반복.
- 보통 뒤에서부터 정렬된 리스트를 보며, 자신보다 작은 데이터를 만나면, 해당 데이터 뒤에 바로 삽입함.
- 따라서 거의 정렬되어 있는 상태인 경우, 더욱 빠르게 동작함.
arr = [1, 0, 3, 4, 5, 9, 6, 8, 2, 7]
# 삽입 정렬 구현 코드
for i in range(1, len(arr)): # 2부터 시작
for j in range(i, 0, -1): # 맨 뒤부터 1씩 감소함
if arr[j] < arr[j-1]: # 자기보다 크면 자리 바꾸며 한 칸씩 앞으로 감
arr[j-1], arr[j] = arr[j], arr[j-1]
else: # 자기와 같거나 작으면 중단함
break
print(arr)- 삽입 정렬은 O(n^2) 이지만 자리를 옮겨야 하는 경우만 위치 변경이 일어나므로, 거의 정렬된 리스트를 정렬하는 경우는 퀵 정렬과 같은 여타 정렬 방법보다 훨씬 효율적!
- 퀵 정렬: pivot 데이터를 기준으로 하여 기준보다 큰 수와 기준보다 작거나 같은 수로 리스트를 둘로 나누는 과정을 반복. 퀵 정렬은 리스트 내 데이터가 1개인 경우, 이미 정렬된 상태로 간주하고 종료됨.
- 이 때, pivot을 정하는 여러 방식이 존재. 여기서는 리스트의 첫번 째 데이터를 pivot으로 삼는 호어 분할 적용.
- 리스트 가장 첫 원소를 피봇 원소로 정함
- 리스트 두 번 째 요소부터 출발하는 왼쪽 포인터와 리스트 마지막 요소부터 출발하는 오른쪽 포인터를 순회하며, 왼쪽에서 피봇보다 큰 데이터를 찾고, 오른쪽에서 피봇보다 작은 데이터를 찾아 위치 교환.
- 왼쪽 포인터와 오른쪽 포인터가 교차하는 경우, 작은 데이터와 피봇의 위치를 교체하면, 리스트가 피봇보다 작거나 같은 쪽과 피봇보다 큰 쪽으로 divide 됨.
- 나눠진 두 리스트를 대상으로 동일한 동작을 반복.
- 리스트의 길이가 1이 되면, 정렬된 것으로 판단해 종료.
- 이 때, pivot을 정하는 여러 방식이 존재. 여기서는 리스트의 첫번 째 데이터를 pivot으로 삼는 호어 분할 적용.
arr = [1, 0, 3, 4, 5, 9, 6, 8, 2, 7]
# 전통적인 퀵 정렬 구현 코드
def quick_sort(arr, start, end):
if start >= end: # 원소가 1개인 경우 종료
return
pivot = start
left = start + 1
right = end
while left <= right: # 교차할 때까지 반복
# 왼쪽 포인터에서 작은 요소는 가만히 둠
while left <= end and arr[left] <= arr[pivot]:
left += 1
# 오른쪽 포인터에서 큰 요소는 가만히 둠
while right > start and arr[right] >= arr[pivot]:
right += 1
# 교차하는 경우, 작은 요소를 피봇과 바꿈
if left > right:
arr[right], arr[pivot] = arr[right], arr[pivot]
# 그 외의 경우는 왼쪽 포인터가 찾은 큰 요소와 오른쪽 포인터가 찾은 작은 요소 교체
else:
arr[left], arr[right] = arr[right], arr[left]
# 나뉜 두 부분에 대해 재귀적으로 정렬 호출
quick_sort(arr, start, right-1)
quick_sort(arr, right+1, end)
quick_sort(arr, 0, len(arr)-1)
print(arr)- 시간복잡도: O(nlogn)
- 보통 시간복잡도 O(nlogn), 최악의 경우 O(n^2)
- 특히 이미 데이터가 정렬되어 있는 경우 최악으로 느리게 동작함.
- 시간복잡도는 살짝 높지만, 더 간략한 방식으로 파이썬스러운 퀵 정렬 코드를 구현할 수 있음.
# 파이썬 다운 퀵 정렬: 시간 복잡도는 좀 더 떨어짐
def quick_sort(arr):
if len(arr) <= 1:
return
pivot = arr[0]
tail = arr[1:]
left = [x for x in tail if x <= pivot]
right = [x for x in tail if x > pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
print(quick_sort(arr))- 계수 정렬: 모든 데이터가 정수 형태로 표현되었을 때만 사용 가능한 매우 빠른 정렬 알고리즘.
- (데이터의 범위 크기) 길이의 별도의 리스트를 값 0으로 선언하고, 리스트 전체를 순회하며 등장 횟수를 셈
- 이후 별도의 리스트를 순회하며 앞에서부터 등장 횟수대로 출력하면 됨
- 시간 복잡도: 최악의 경우에도 O(n+k), k = 데이터 범위 크기
- 데이터 크기가 한정되어있고 데이터 크기가 많이 중복되어있을 수록 효율적인 정렬 방법임
arr = [1, 0, 3, 4, 5, 9, 6, 8, 2, 7]
# 계수 정렬 구현 코드
count = [0] * (max(arr) + 1)
for v in arr:
count[v] += 1
for i in range(len(count)):
for v in count:
print(i, end= ' ')