퀵 정렬, 계수 정렬, 파이썬 정렬 라이브러리
#퀵 정렬, #계수 정렬, #Quick_Sort, #Count_Sort, #Python_sorted()
퀵 정렬
퀵 정렬Quick sort은 지금까지 배운 정렬 알고리즘(선택 정렬, 삽입 정렬, 퀵 정렬) 중에서 가장 많이 사용되는 정렬 알고리즘이다. 퀵 정렬은 어째서 이름부터가 '빠른 정렬 알고리즘'일까?
퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 원리를 이해하면 다른 고급 정렬 기법인 병합 정렬, 힙 정렬 등에 비해 쉽게 소스코드를 작성할 수가 있다. 퀵 정렬에서는 피벗pivot이 사용된다. 피벗이란 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'이다. 가장 대표적인 분할 방식인 호어 분할Hoare Partition** 방식을 따르면 **리스트에서 첫 번째 데이터를 피벗으로 정한다. 피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 그 다음 큰 데이터와 작은 데이터의 위치를 서로 교환해준다. 이러한 과정을 반복한다. 이를 반복하다 보면 왼쪽에서부터 찾는 '큰 값'과 오른쪽에서부터 찾는 '작은 값'이 서로 엇갈리는 시점이 온다. 이렇게 두 값이 엇갈린 경우에는 '작은 값'과 피벗의 위치를 서로 변경한다. 이렇게 피벗이 리스트의 중간에 위치하게 되면 피벗을 기준으로 왼쪽과 오른쪽 두 개로 리스트가 분할Divide(=파티션Partition)된다. 분할된 두 리스트에 대하여 각각 피벗을 새로 설정하고 과정을 반복하다보면 '재귀 함수'와 똑같이 동작하게 된다. 이 때 재귀 함수의 종료조건은 바로 현재 리스트의 데이터 개수가 1개인 경우이다. 데이터의 개수가 1개이면 이미 정렬이 되어 있다고 간주할 수 있고 분할이 불가능하기 때문이다.
퀵 정렬은 두 가지 형태의 소스코드로 작성해볼 수 있다. 하나는 가장 널리 사용되고 있는 직관적인 형태의 퀵 정렬 소스코드이고, 하나는 파이썬의 장점을 살려 짧게 작성한 퀵 정렬 소스코드이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Python code
# 퀵 정렬
array = [5,2,1,6,3,4,9,7,8,0]
def quick_sort(array, start, end):
if start >= end: # 원소가 1개인 경우 종료
return
pivot = start # 피벗은 첫 번째 원소
left = start + 1
right = end
while left 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]
# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
quick_sort(array, start, right - 1)
quick_sort(array, right + 1, end)
quick_sort(array, 0, len(array)-1)
print(array) # -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
1
2
3
4
5
6
7
8
9
10
11
12
13
# Python code
# 퀵 정렬, 파이썬다운 소스코드
array = [5,2,1,6,3,4,9,7,8,0]
def quick_sort(array):
# 리스트가 하나 이하의 원소만을 담고 있다면 종료
if len(array) pivot] # 분할된 오른쪽 부분
# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
return quick_sort(left_side) + [pivot] + quick_sort(right_side)
print(quick_sort(array)) # -> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
퀵 정렬의 시간 복잡도 퀵 정렬은 평균적으로 O(NlogN)의 시간 복잡도를 가지고, 최악의 경우(이미 데이터가 정렬되어 있는 경우)는 위 코드의 시간복잡도가 O(N2)이다. 따라서 데이터가 이미 많이 정렬되어 있는 경우에는 최선의 경우 O(N)의 시간복잡도를 가질 수 있는 삽입정렬을, 데이터가 아직 많이 정렬되어 있지 않았을 경우에는 평균적으로 O(NlogN)의 시간복잡도를 가지는 퀵 정렬을 사용하면 된다.
- '모든 범위를 담을 수 있는 크기의 리스트(배열)을 선언'하고 0으로 초기화한다. 예를 들어 데이터가 1002011112 이면 0000000000 인 리스트를 선언한다.
- 전체 데이터(N개)를 하나씩 확인하면서 리스트의 동일한 인덱스가 가지는 계수를 1씩 증가시킨다.예를 들어 1이 다섯 번 확인된다면 리스트의 1 인덱스에는 +1 +1 +1 +1 +1 = 5 가 기록된다.
- 전체 데이터 확인을 마치고 업데이트 된 리스트를 가장 작은 인덱스부터 해당하는 계수 횟수만큼 꺼낸다.예를 들어 [3,5,2]이면 0001111122 이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Python code
# 계수 정렬
# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [5,2,1,6,2,3,5,4,9,7,1,2,8,0]
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)
for i in range(len(array)):
count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 계수 값 증가
for i in range(len(count)): # 리스트에 기록된 계수 정보 확인
for j in range(count[i]): # 계수 횟수 만큼 인덱스 값 출력
print(i, end = ' ') # 띄어쓰기를 구분으로 출력 -> 0 1 1 2 2 2 3 4 5 5 6 7 8 9
계수 정렬의 시간 복잡도 O(N+K)
계수 정렬의 공간 복잡도 O(N+K)
추가) 계수 정렬은 항상 사용할 수 있는 알고리즘은 아니며, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다. 예를 들어 리스트의 크기가 100만 개가 되도록 선언해야 하는 경우는 사용이 어렵고, 성적과 같이 100점을 맞은 학생이 여럿일 수 있는 중복값이 많은 데이터에는 사용을 고려해봄직 하다. 그러나 결론적으로는, 데이터의 크기가 너무 크거나 데이터의 특성을 파악하기 어렵다면 일반적으로 퀵 정렬이 안전하다. **
파이썬의 정렬 라이브러리
꼭 정렬 기법의 원리를 묻거나 이를 알고있어야만 풀 수 있는 문제가 아니라면 파이썬의 정렬 라이브러리를 사용하는 것이 가장 성능이 좋고, 사용하기도 빠르고 쉽다. 정렬 라이브러리는 최악의 경우에도 시간 복잡도 O(NlogN)을 보장하도록 최적화가 되어있다. 또한 정렬 라이브러리에는 key를 매개변수로 받거나 람다Lambda** 함수**를 사용할 수도 있다. 정렬함수는 array.sort() 또는 result = sorted(array) 이렇게 두 가지 사용법이 있다.
다음은 key를 사용하는 소스코드이다.
1
2
3
4
5
6
7
8
9
10
11
# Python code
# 파이썬 정렬 라이브러리 sort(key = ~), sorted(array, key = ~).
array = [('선택정렬', 'O(N^2)', 4), ('삽입정렬', 'O(N)~O(N^2)', 3), ('퀵정렬', 'O(NlogN)~O(N^2)', 2), ('계수정렬', 'O(N+K)', 1)]
# 자체 함수 선언하는 key
def setting(data):
return data[2]
result = sorted(array, key = setting)
print(result) # -> [('계수정렬', 'O(N+K)', 1), ('퀵정렬', 'O(NlogN)~O(N^2)', 2), ('삽입정렬', 'O(N)~O(N^2)', 3), ('선택정렬', 'O(N^2)', 4)]
1
2
3
# 람다 함수 사용하는 key
result = sorted(array, key = lambda data: data[2])
print(result) # -> [('계수정렬', 'O(N+K)', 1), ('퀵정렬', 'O(NlogN)~O(N^2)', 2), ('삽입정렬', 'O(N)~O(N^2)', 3), ('선택정렬', 'O(N^2)', 4)]
위의 array 리스트에는 지금까지 다룬 정렬 알고리즘의 빠른 순서대로 순위를 매겨서 sort함수를 사용해 그 순서대로 오름차순으로 출력되게 해보았다. 내림차순으로 하고 싶을 경우 reverse 매개변수에 True를 넣어주면 된다.
이 글의 내용이 많은 도움이 된다면 아래 책을 사서 읽어보고 공부하는 것을 추천한다.
이것이 취업을 위한 코딩 테스트다 with 파이썬
1
2
3
4
5
6
저자
나동빈
출판
한빛미디어
발매
2020.08.05.