1. 알고리즘 및 코드
Problem : 오름차순으로 주어진 리스트를 정렬
Input : 양의 정수 n, 리스트 S
Output : 오름차순으로 정렬된 리스트 S
알고리즘)
1. pivot을 기준으로 나눈다.
2. 나눈 pivot의 왼쪽, 오른쪽을 재귀적으로 다시 적용한다.
3. 리스트를 더 이상 나눌 수 없을 때까지 반복한다. (원소가 1개 이하로 남았을 때)
생각의 흐름)
pivot은 리스트의 맨 앞을 넣는다.
pivot을 기준으로 나누면 되는데, j에 low 위치를 넣고, i를 low + 1의 위치부터 high까지 넣는다.
그러면 for문으로 i를 돌리고, 이때 S[i]가 pivot보다 작으면 j에 1을 더하고, i 위치와 j 위치를 swap한다.
쭉 반복하면 결국 최종적으로 j의 위치가 pivot보다 작은 애 중 가장 멀리가 있는 녀석임
고로 pivot과 S[j]를 스왑해주면 끝
코드, Python)
import sys
import time
input = sys.stdin.readline
n = int(input())
S = list(map(int, input().split()))
# globals()['count'] = 0
count = 0
def partition(low, high):
# pivot을 기준으로 나누는 함수
global count
count += 1
# globals()['count'] += 1
pivot = S[low]
j = low
for i in range(low + 1, high + 1):
if S[i] < pivot:
j += 1
S[i], S[j] = S[j], S[i]
S[j], S[low] = S[low], S[j]
return j
def quicksort(low, high):
# 리스트를 정렬하는 함수
if low < high:
pivotindex = partition(low, high)
quicksort(low, pivotindex - 1)
quicksort(pivotindex + 1, high)
s = time.time()
quicksort(0, n-1)
e = time.time()
print(count)
print(*S)
print("\n", e - s)
2. 시간 복잡도 분석
참고로 quicksort의 every-case time complexity로는 불가능합니다. 들어오는 리스트에 따라 시간 복잡도가 달라지기 때문에입니다.
아 그래도 partition 함수의 일정 시간 복잡도는 n-1입니다. 왜냐면 비교는 항상 n-1번 하니까요. 리스트 원소의 크기에 상관없이
worst-case로 비교할 때)
worst-case는 pivot이 항상 작은 애가 될 때, 즉 이미 리스트가 정렬되어 있을 때
basic operation : S[i]와 pivot의 비교 연산
input size : n
고로 \(W(n)\,=\,W(0)+W(n-1)+n-1\)이 되겠습니다.
W(0)는 왼쪽 배열을 정렬하는 시간, 즉 0이 됩니다.
W(n-1)은 오른쪽 배열을 정렬하는 시간이고, n-1은 비교 연산의 시간입니다.
점화식을 이용해서 풀면 \(W(n)\,=\,\frac{n(n-1)}{2}\)이 되겠습니다 !
즉 최악의 경우 \(\Theta(n^2)\)이네요..
엥; 이름이 quick sort인데 왤케 느리죠;;
하지만 average-case time complexity는 얘기가 다릅니다.
average-case time complexity)
최악의 경우에는 pivot이 항상 작은 애가 됐지만, 평균의 경우에는 pivot이 리스트 안의 어느 수가 될지 아무도 모른다고 가정합니다.
이때는 평균적으로 pivot을 기준으로 반반 나뉜다고 생각하시면 됩니다.
따라서 평균적인 경우에는 \(A(n)\,=\,\frac{2}{n}\times W(\frac{n}{2})+n-1\)입니다.
참고로 2는 \(\frac{n}{2}\)가 두 개 있기 때문이지만, \(\frac{1}{n}\)은 리스트 안의 숫자 중 어느 수가 pivot이 될지 모르기 때문에 확률 값을 곱한 것입니다.
자세한 내용은 생략하지만, 이 시간 복잡도는 \(\Theta(n lgn)\)에 속합니다.
상당히 빠르죠?? 그래서 quick sort입니다.
3. 여담
급 궁금해져서 globals()['count']와 그냥 global 키워드로 참조하는 것 중에 뭐가 더 빠를까를 테스트 했습니다.
당연히 전자가 빠를 줄 알았는데, 후자가 아주 약~~간 더 빠르네요.
큰 차이는 안 나서 상관은 없습니다만, 많이 헤비한 프로그램을 돌린다면 얘기가 달라지겠네요.
아무튼 감사합니다.
지적 환영합니다.