20241127 이것이 코딩 테스트다 챕터6(정렬)
정렬 알고리즘
데이터를 특정한 기준에 따라서 순서대로 나열하는 것.
정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해짐. 즉, 정렬 알고리즘은 이진 탐색의 전처리 과정.
정렬 알고리즘을 통해 ‘알고리즘의 효율성’을 이해할 수 있음.
선택 정렬 (Selection Sort)
매번 ‘가장 작은 것’을 선택.
데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 방식으로 정렬하는 것.
가장 원시적인 방법.
시간복잡도 데이터 개수 N일때, O(N^2).
다른 정렬 알고리즘과 비교했을 때, 선택정렬은 O(N^2)의 시간복잡도를 가지기 때문에 매우 비효울적임. 하지만 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩테스트에서 잦기 때문에 코드 형태에 익숙해질 필요가 있음.
- 구현 방법
array = [...]
for i in range(len(array)): #1
min_index = i #2
for j in range(i+1, len(array)): #3
if array[min_index] > array[j]:
min_index = j #3-1
array[i], array[min_index[ = array[min_index], array[i] #4
- list의 길이동안 정렬되지 않은 데이터에 관해 2~4 반복
- 정렬되지 않은 데이터 중 가장 왼쪽 데이터를 가장 작은 원소라 가정하고 해당 원소의 인덱스
min_index로 저장 - 정렬되지 않은 데이터 중 두번째 왼쪽 데이터부터 끝까지 min_index에 해당하는 원소와 크기 비교
3-1. 현재 min_index에 해당하는 원소보다 작은 원소가 있으면 해당 인덱스로 min_index 업데이트 - 가장 왼쪽 데이터와 min_index에 해당하는 원소의 위치 스왑
파이썬에서 스왑은
array[0], array[1] = array[1], array[0]로 간단히 가능.
다른 언어에서는 임시 변수를 만들어 스왑해야 됨.
삽입 정렬 (Insertion Sort)
특정한 데이터를 ‘적절한 위치’에 삽입.
데이터가 적절한 위치에 들어가기 전, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정하고 데이터를 하나씩 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에 그 위치에 삽입하는 방식으로 정렬하는 것.
선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸지만 삽입 정렬은 그렇지 않음.
즉, 필요할 때만 위치를 바꾸기 떄문에 ‘데이터가 거의 정렬되어 있을 때’ 훨씬 효율적임.
시간복잡도 데이터 개수 N일때, O(N^2).
하지만 현재 리스트의 데이터가 거의 정렬되어 있는 경우에는 어떤 정렬 알고리즘보다 삽입 정렬 알고리즘이 가장 강력함. 최선의 경우 O(N)의 시간 복잡도를 가짐.
- 구현방법
array = [...]
for i in range(1, len(arrar)): #1
for j in range(i, 0, -1): #2
if array[j] < array[j-1]:
array[j], array[j-1] = array[j-1], array[j] #2-1
else:
break #2-2
- list의 두번째 데이터부터 끝까지 정렬되지 않은 데이터에 관해 2~2-2 반복
- 정렬되지 않은 데이터의 인덱스부터 인덱스 1까지 1씩 감소시키면서 현재 위치의 값과 하나 왼쪽 값 크기 비교
2-1. 왼쪽 값보다 현재 위치 값이 작으면 왼쪽 값이랑 현재 위치 값 스왑
2-2. 왼쪽 값이 더 작으면 그 위치에서 멈춤
퀵 정렬
피벗이라는 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방식으로 빠르게 정렬하는 것.
가장 많이 사용되는 알고리즘.
피벗을 설정하고 리스트를 분할하는 방법에 따라 퀵 정렬을 구분함.
- 호어 분할 방식 : 리스트에서 첫 번째 데이터를 피벗으로 정함.
호어 분할 방식
- 피벗 : 리스트에서 첫 번째 데이터
피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾음. 큰 데이터와 작은 데이터의 위치를 서로 교환.
피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행하므로 ‘재귀 함수’ 형태로 작성했을 때 구현이 매우 간결해짐.
시간복잡도 평균은 O(NlogN) 최악은 O(N^2).
데이터가 무작위로 입력되어 있을 때는 매우 빠른편. 데이터 개수가 많을수록 선택 정렬, 삽입 정렬에 비해 퀵 정렬이 압도적으로 빠르게 동작.
이미 데이터가 정렬되어 있는 경우에는 매우 느리고 동작. 따라서 기본 정렬 라이브러리를 이용해 O(NlogN)을 보장함.
- 구현방법
array = [...]
def quick_sort(array, start, end): #1
if start >= end: #2
return #3
pivot = start #4
left = start + 1 #5
right = end #6
while left <= right: #7
while left <= end and array[left] <= array[pivot]: #8
left += 1 #8-1
while right > start and array[right] >= array[pivot]: #9
right -= 1 #9-1
if left > right: #10
array[right], array[pivot] = array[pivot], array[right] #10-1
else: #11
array[left], array[right] = array[right], array[left] #11-1
quick_sort(array, start, right - 1) #12
quick_sort(array, right + 1, end) #13
quick_sort(array, 0, len(array) - 1) #14
- 재귀 위한 함수 정의. start와 end는 숫자로 인덱스 의미. start는 0, end는 len(array)-1
- 원소가 1개인 경우 (재귀 종료 조건)
- 함수(정렬) 종료
- 피벗 첫 번째 원소로 설정
- 피벗 제외 왼쪽 인덱스
- 오른쪽 인덱스
- 왼쪽 인덱스가 오른쪽 인덱스보다 커지지 않는 동안, 즉 엇갈리지 않는 동안
- 왼쪽에서부터는 피벗보다 큰 데이터를 찾는다. 따라서 left가 리스트의 크기를 넘어가지 않고 왼쪽 데이터가 피벗보다 작거나 같으면 8-1. 넘어감. 왼쪽 인덱스 1 증가
- 오른쪽에서부터는 피벗보다 작은 데이터를 찾는다. 따라서 right가 피벗이 되지 않고 오른쪽 데이터가 피벗보다 크거나 같으면 9-1. 넘어감. 오른쪽 인덱스 1 감소
- 엇갈렸다면 10-1. 오른쪽에서부터 찾은 작은 데이터와 피벗을 스왑. 피벗의 왼쪽에는 피벗보다 작은 데이터가, 피벗의 오른쪽에서 피벗보다 큰 데이터가 위치하게 됨(분할). 엇갈렸으므로 7번 while문 종료
- 엇갈리지 않았다면 11-1. 왼쪽에서부터 찾은 큰 데이터와 오른쪽에서부터 찾은 작은 데이터를 스왑
- 분할 이후 right은 피벗 인덱스인 상태. 피벗의 왼쪽 부분에서 정렬 수행
- 피벗의 오른쪽 부분에서 정렬 수행
- array에 관해 퀵 정렬 시작
cf. 파이썬 장점 살린 퀵 정렬
array = [...]
def quick_sort(array): #1
if len(array) <= 1: #2
return array #3
pivot = array[0] #4
tail = array[1:] #5
left_side = [x for x in tail if x <= pivot] #6
right_side = [x for x in tail if x > pivot] #7
return quick_sort(left_side) + [pivot] + quick_sort(right_side) #8
print(quick_sort(array)) #9
- 재귀 위한 함수 정의
- 리스트가 하나 이하의 원소만을 담고 있으면
- 함수(정렬) 종료
- 피벗은 첫 번째 원소
- 피벗을 제외한 리스트
- 피벗보다 작은 데이터로 구성된 분할된 왼쪽 부분
- 피벗보다 큰 데이터로 구성된 분할된 오른쪽 부분
- 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
- array는 정렬된 array가 아님. quick_sort(array)가 정렬된 array
시간 면에서는 전통 퀵 정렬의 분할 방식보다 조금 비효율적이지만, 더 직관적이고 기억하기 쉬움.
Leave a comment