3. 퀵 정렬
· 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.
· 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다.
· 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다.
· 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다.
맨 처음 피벗의 값은 '5'다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택된다. 그 뒤, 이 두 데이터의 위치를 서로 변경한다.
현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '9'가 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '2'가 선택된다. 그 뒤, 이 두 데이터의 위치를 서로 변경한다.
현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '6'이 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '1'이 선택된다. 단, 이처럼 위치가 엇갈리는 경우 '피벗'과 '작은 데이터'의 위치를 서로 변경한다.
[분할 완료] 이제 '5'의 왼쪽에 있는 데이터는 모두 5보다 작고, 오른쪽에 있는 데이터는 모두 '5'보다 크다는 특징이 있다. 이렇게 피벗을 기준으로 데이터 묶음을 나누는 작업을 분할(Divide) 혹은 파이션(Partition)이라고 한다. 그 뒤, '5'를 기준으로 왼쪽에 있는 데이터들과 오른쪽에 있는 데이터들을 각각을 하나의 배열로 판단을 해서 정렬을 수행한다.
[왼쪽 데이터 묶음 정렬] 왼쪽에 있는 데이터에 대해서 마찬가지로 정렬을 수행한다. 첫 번째 원소 '1'이 피벗으로 설정이 되고, 왼쪽에서부터 피벗보다 큰 '4'를 선택하고, 오른쪽에서부터 피벗보다 작은 '0'이 선택되어 위치를 서로 변경한다.
[오른쪽 데이터 묶음 정렬] 오른쪽에 있는 데이터에 대해서 마찬가지로 정렬을 수행한다.
이러한 과정을 반복하면 전체 데이터에 대해서 정렬이 수행된다.
이처럼 퀵 정렬이 수행되는 과정은 재귀적으로 수행이 된다. 수행될 때마다 정렬의 범위가 점점 좁아진다.
퀵 정렬이 빠른 이유: 직관적인 이해
· 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(NlogN)을 기대할 수 있다.
퀵 정렬의 시간 복잡도
· 퀵 정렬은 평균의 경우 O(NlogN) 의 시간 복잡도를 가진다.
· 하지만 최악의 경우 O(N2) 의 시간 복잡도를 가진다.
(첫 번째 피벗값을 어떻게 설정하는가에 따라서 분할이 절반에 가깝게 이루어지지 않고 한 쪽에 편향된 분할이 발생할 수 있다.)
ex) 첫 번째 원소를 피벗으로 삼을 때, 이미 정렬된 배열에 대해서 퀵 정렬을 수행
맨 처음 피벗을 '0'으로 설정하면 1~9까지가 새로운 배열로 분할된다. 다음도 마찬가지로 '1'을 피벗으로 설정하고 2~9까지가 새로운 배열로 분할된다. 이렇게 탐색하는데 N, 분할이 이루어질 때마다 N의 시간 복잡도를 가지게 된다.
퀵 정렬 코드
array = list(map(int, input().split()))
def quick_sort(array, start, end):
# 원소가 1개인 경우 종료
if start >= end:
return
# 첫 번째 원소가 피벗
pivot = start
left = start + 1
right = end
while left <= right:
# 왼쪽에서부터 피벗보다 큰 데이터를 찾을 때까지 오른쪽으로 이동
while left <= end and array[left] <= array[pivot]:
left += 1
# 오른쪽에서부터 피벗보다 작은 값을 찾을 때까지 왼쪽으로 이동
while right > start and array[right] >= array[pivot]:
right -= 1
# 엇갈렸으면 피벗값과 작은 값을 교체
if left > right:
array[right], array[pivot] = array[pivot], array[right]
# 엇갈리지 않았다면 작은 데이터와 큰 데이터의 위치를 교체
else:
array[left], array[right] = array[right], array[left]
print(array)
# 분할 이후 왼쪽 부분과 오른쪽 부분을 각각 정렬 수행
quick_sort(array, start, right-1)
quick_sort(array, right+1, end)
quick_sort(array, 0, len(array)-1)
print("result : ", array)
4. 계수 정렬
· 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘
· 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용가능
· 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N + K)를 보장한다.
가장 작은 데이터는 '0' 가장 큰 데이터는 '9'인 것을 확인할 수 있다.
이런 상황에서 가장 작은 데이터부터 가장 큰 데이터까지 모두 담길 수 있는 크기로 리스트를 초기화한다. 여기서 인덱스가 각각의 값에 해당하는 것이다.
그리고 데이터에서 각 인덱스가 몇번이 나왔는지 갯수를 센다.
데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다. 먼저 제일 앞에 있는 데이터 '7'을 확인하면 인덱스 '7'의 개수값을 1 증가시킨다.
마찬가지로 2번째 데이터는 '5'를 확인하여 인덱스 '5'의 개수값을 1 증가시킨다.
모든 데이터에 대해서 위 과정을 반복했을 때 최종적으로 위 사진과 같은 카운트 테이블이 갱신된다.
카운트를 모두 구한 뒤에는 실제로 정렬 수행 결과를 확인할 수 있다.
정렬 수행 결과를 확인할 때는 리스트의 첫 번째 인덱스부터 개수값만큼 반복하여 출력한다.
계수 정렬 코드
# 모든 원소의 값이 0보다 크거나 같다고 가정
array = list(map(int, input().split()))
# 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)
# 각 데이터에 해당하는 인덱스의 값 증가
for i in range(len(array)):
count[array[i]] += 1
print("count : ", count)
# 리스트에 기록된 정렬 정보 확인
for i in range(len(count)):
for j in range(count[i]):
print(i, end=" ")
첫 번째 반복문의 경우 데이터의 개수만큼 데이터를 확인하면서 카운트 값을 체크한다. 그러므로 O(N) 만큼의 시간 복잡도를 가진다.
그 다음 2번째 반복문의 경우 인덱스의 가장 큰 값을 의미하는 K만큼의 복잡도와 안쪽의 반복문(j)의 경우 전체 수행 횟수 N만큼의 복잡도를 가지므로 O(N+K)의 시간복잡도를 가진다.
계수 정렬의 복잡도 분석
· 계수 정렬의 시간 복잡도와 공간 복잡도는 모두 O(N+K)이다.
· 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다.
ex) 데이터가 0과 999,999로 단 2개만 존재하는 경우
· 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 동작한다.
ex) 성적의 경우 100점을 맞은 학생이 여러 명일 수 있기 때문에 계수 정렬이 효과적이다.
정렬 알고리즘 비교하기
'코딩테스트 준비 > 이것이 코딩테스트다 개념정리' 카테고리의 다른 글
| 최단 경로 알고리즘 - 플로이드 워셜 알고리즘 (0) | 2023.06.30 |
|---|---|
| 최단 경로 알고리즘 - 다익스트라 알고리즘(Dijkstra Algorithm) (0) | 2023.06.30 |
| 이진 탐색 (1) | 2023.06.15 |
| 정렬 알고리즘 (1) [선택 정렬, 삽입 정렬] (1) | 2023.06.15 |
| 다이나믹 프로그래밍 (0) | 2023.06.15 |