이전 글이었던 선택정렬과 삽입정렬에 이어 오늘은 퀵정렬과 계수정렬을 소개하고자 한다.
앞선 두 정렬은 정렬 알고리즘중에서는 속도가 느린편에 속한다. 물론 거의 정렬이 되어있는 리스트에서의 삽입정렬은 매우 효과적이지만 그것은 아주 제한적인 조건이며, 범용적으로는 느린편에 속하는 알고리즘이다.
그 중 퀵정렬은 앞선 두 알고리즘과 마찬가지로 빅-O 표기법에서의 시간복잡도는 O(N^2) 이다. 여기서 시간복잡도가 같은데 어떻게 더 효과적이라고 할 수 있는지에 대해서 짚고 넘어가자면, 빅-O 표기법은 최악의 경우에서의 시간복잡도를 나타낸다. 따라서 거의 정렬되어있는 경우에서의 삽입정렬이 O(N) 에 수렴하는 시간복잡도를 보여주기도 하지만, O(N^2) 로 나타내는 것이다.
퀵정렬도 마찬가지로 최악의 경우, 이미 완전히 정렬되어있는 오름차 혹은 내림차 리스트는 O(N^2) 의 시간복잡도를 가진다. 하지만 이 경우는 단 2개의 경우의 수로 리스트 원소의 수가 조금만 늘어나도 거의 무의미한 경우의 수가 된다. 따라서 빅-O 표기법 상으로는 O(N^2) 이지만, 평균적으로 O(NlogN) 의 시간복잡도를 가진다.
퀵 정렬의 정렬알고리즘은 다음과 같다.
퀵정렬은 기준을 정하고, 그 기준보다 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.
- 정렬하고자 하는 리스트의 첫번째 데이터를 피벗( 기준 ) 으로 사용한다.
- 리스트 앞쪽부터 뒷 방향으로 피벗보다 큰 첫번째 데이터를 찾고, 뒷쪽부터 앞 방향으로 반대로 피벗보다 작은 첫번째 데이터를 찾아 그 둘을 교환한다.
- 만약 진행 중 앞에서 오름차순 인덱스와 뒤에서 내림차순 인덱스가 엇갈릴 경우 더 작은 데이터값과 피벗값을 교환한다.
- 3 의 교환이후 피벗을 기준으로 큰값과 작은 값의 두개의 리스트로 분리
- 분리 된 리스트에서 각각 재귀함수를 통해 1 부터 다시 실행 => 분리 된 리스트의 길이가 1 이 될 때 까지
역시나 알고리즘을 글로 설명해서는 이해가 쉽게 되지 않을 수 있다. 따라서 그림으로 간단하게 설명하자면 다음과 같다.
노란색은 현재 피벗, 파란색과 화살표는 현재 탐색된 조건 별 원소, 초록색은 정렬 완료된 원소를 뜻한다.
1번 - 피벗 "5" 보다 큰 첫번째 원소 "7" 과 피벗보다 작은 첫번째 원소 "4" 를 교환한다.
3번에서 탐색 인덱스가 엇갈린다. 따라서 엇갈린 두 인덱스 중 작은 값 "1" 과 피벗을 교환한다.
3번까지의 정렬을 통해 "5" 를 기준으로 좌 5칸 우 4칸의 리스트가 새로 생성된다. 4번부터는 우선적으로 왼쪽 리스트를 다시 정렬한다. 6번에 이르러 현재 피벗 "2" 보다 작은 현재 탐색된 원소가 없다. 따라서 그 자리에 정렬 완료한다. 마찬가지로 7번에서 단 한개 있는 원소"3" 이 피벗 "4" 보다 작은값이므로 위치를 바꾸고 정렬 완료한다.
간단하지만 확실한 알고리즘을 통해 정렬이 완료되었다. 이 알고리즘의 특징이라고 한다면, 피벗과 재귀함수일 것이다. 절반으로 나누어가며 빠르게 정렬을 해주는 퀵정렬이지만 앞서 말한대로 만약 이미 정렬되어있는 데이터라면, 매우 비효율적인 정렬효율을 보여준다. 위의 알고리즘을 코드로 옮긴다면 다음과 같다.
array = [5,7,9,0,3,1,6,2,4,8]
n = len(array)
def quick_sort(array, start, end):
if start >= end: #리스트의 길이가 1 이라면 실행하지 않음.
return
left, right = start+1,end #오름차 탐색 인덱스와 내림차 탐색 인덱스 설정
pivot = start
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[pivot],array[right] = array[right],array[pivot]
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,n-1)코드의 단순 길이만 보더라도 앞선 두 알고리즘보다는 훨씬 길다는것을 알 수 있다. 2중 While 문이 사용되었고 마지막엔 재귀함수까지 사용되므로 코드의 길이로나, 복잡함으로나, 앞선 두 알고리즘보다는 복잡한 편이다. 하지만 이를 이용한 정렬속도가 평균 O(NlogN) 을 보장하므로, 대부분의 상황에서 좋은 퍼포먼스를 보여준다.
다음으로 소개할 정렬방법은 계수정렬이다. 해당 알고리즘의 시간복잡도는 O(N+K) 이다. 여기서 K 는 데이터 중 최댓값이다. 다시 정확히 얘기하자면 데이터 중 최대 인덱스 즉 길이가 아닌 데이터 내에 있는 원소의 최댓값을 말한다. 이는 계수정렬의 독특하지만 원시적인 정렬방법때문이다. 계수정렬은 전체 데이터를 순회하며 각 수의 갯수를 세고 그대로 출력한다.
계수정렬의 알고리즘은 다음과 같다.
- 데이터 내 가장 큰 max 값을 찾는다.
- 0부터 max번 인덱스까지 0으로 초기화된 리스트(LIST)를 생성한다.
- 데이터의 맨 처음부터 끝까지 순회하며 각 원소의 값에 해당하는 (LIST) 의 인덱스에 COUNT 해준다.
- 모두 취합이 끝난 (LIST) 를 0번 인덱스부터 COUNT 된 횟수만큼 출력한다.
보다시피 상당히 간단하고 반복또한 없다. 특이점이 있다면, 새로운 리스트(LIST) 를 생성하고 그 리스트에 매 원소에 해당하는 인덱스값에 1을 더해준다는 것 뿐. 이를 그림으로 설명하자면 다음과 같다.
위와같이 데이터 중 가장 큰 값인 9까지의 리스트를 생성하고 데이터를 순회하며 각 원소마다 해당 원소 인덱스값에 1을 더해준다. 이와같은 작업이 끝나고나면, LIST = [2,2,2,1,1,2,1,1,1,2] 의 리스트가 반환된다. 따라서 이제 반환된 리스트를 가지고 순서대로 출력하면 정렬된 리스트가 반환된다.
해당 알고리즘을 코드로 옮기면 다음과 같다.
array = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
count = [0]*(max(array)+1)
for i in range(len(array)):
count(array[i]) += 1
for i in range(len(count)):
print(i, end=' ')단순한 for 문 2번으로 해당 정렬이 끝난다. 간결한 코드만큼 데이터가 한정되어있기만 하다면, 현존 정렬 알고리즘 중 가장 빠르게 동작한다.
하지만, 중요한 점은 데이터가 한정되지 않았다면 심각한 비효율성을 가진다. 마치 0과 1e9 두 원소만을 가진 리스트라면 1e9 개의 원소가 없음에도 리스트를 1e9 크기로 선언해야하므로, 속도도 느리지만 메모리또한 비효율적으로 사용하게 된다.
[[ 마무리 ]]
사실 정렬알고리즘은 테스트에서는 흔히 사용되는 알고리즘은 아니며 복잡한 편도 아니다. 그리고 대부분 기본적으로 주어지는 라이브러리인 sort 를 사용해도 문제가 없는경우가 대다수이기때문에 문제에서 만나보기엔 어렵다. 하지만 정렬을 공부하며 현재 짜고자 하는 코드에서도 어느 부분에 의해 시간이 낭비되고 메모리가 낭비되는지 대충 이해할 수 있다.
다음으로는 [다이나믹 프로그래밍] 을 업로드하지 않을까 싶다.
최근댓글