정렬 중에서 퀵정렬에 대해서 알아보겠습니다. 2가지의 방식이 있습니다.
방법1.
1단계. 입력된 임의의 원소를 피벗으로 선택합니다. 피벗은 기준이 되는 원소입니다.
2단계. 피벗을 기준으로 작은 원소들, 피벗과 같은 원소들, 피벗보다 큰 원소들로 나눕니다.
3단계. 재귀적으로 정렬하고 크기순으로 놓으면 끝
파이썬으로 간단히 구현해보면
|
1
2
3
4
5
6
7
8
|
def quick_sort(S):
if len(S) < 2:
return S
pivot = random.choice(S)
L = [x for x in S if x < pivot]
E = [x for x in S if x == pivot]
G = [x for x in S if x > pivot]
return quick_sort(L) + E + quick_sort(G)
|
cs |
먼저 리스트 S에서 랜덤으로 피벗을 구합니다. import random을 하셔야합니다.
L, E, G 집단으로 원소들을 나눠줍니다.
8번째 줄에서 다시 집단들을 재귀적으로 나눠줍니다. 결과적으로 정렬된 리스트를 얻을 수 있습니다.
방법2.
2번째 방식은 새로운 리스트에 합치는것이 아니라 리스트 내에서 피벗을 정해서 정렬하는 방법입니다.
1단계. 랜덤으로 피벗을 정하고 맨 왼쪽에 있는 인덱스와 맨 오른쪽에 있는 인덱스를 선택
2단계. j가 i보다 작고 피벗보다 작으면 교환이 이루어집니다. 이과정을 재귀적으로 반복합니다.
3단계: i가 j보다 크거나 같아지면 가운데에 피벗을 넣어주면 끝
파이썬으로 구현해보면
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
def quick_sort(S, a, b):
if a >= b:
return
pivot_idx = random.randint(a, b)
S[pivot_idx], S[a] = S[a], S[pivot_idx]
pivot = S[a]
left = a+1
right = b
while left <= right:
while left <= right and S[left] < pivot:
left += 1
while left <= right and pivot < S[right]:
right -= 1
if left <= right:
S[left], S[right] = S[right], S[left]
left, right = left + 1, right - 1
S[right], S[a] = S[a], S[right]
quick_sort(S, a, right - 1)
quick_sort(S, right + 1, b)
|
cs |
S는 리스트이고 a와b는 각각 리스트의 양쪽 index입니다.
랜덤인트로 피벗을 정하고 피벗을 맨왼쪽으로 보내줍니다.
그리고 위에서 설명한 방식으로 진행됩니다.
퀵정렬의 수행시간
최선의 경우는 랜덤으로 뽑은 피벗이 항상 중간값을 갖는 경우입니다.
수행시간 T(n) = 2*T(n/2) + cn
위에서 설명한 것처럼 리스트를 두개로 나누기 때문에 2*T(2/n)이 나온거고 cn은 피벗과 비교하는 시간입니다.
계속 2개씩 나눠지기 때문에 최대 log(n)번 나눌 수 있습니다. (이진트리)
따라서 k= log(n) 이므로 O(nlogn)의 수행시간을 가집니다.
최악의 경우는 피벗을 뽑을때마다 최솟값이나 최대값인 경우입니다.
한 쪽으로 기울어진 트리가 만들어지게 됩니다. 따라서 n(n+1)/2 -> O(n^2)의 수행시간이 걸립니다.
따라서 Big-O 표기법으로 시간복잡도는 O(n^2)입니다.
'자료구조' 카테고리의 다른 글
| [파이썬 자료구조] 사전식 정렬(lexicographic sort) (0) | 2020.06.13 |
|---|---|
| [파이썬 자료구조] 버킷정렬(bucket sort) (0) | 2020.06.13 |
| [파이썬 자료구조] 합병정렬 (0) | 2020.06.10 |
| [파이썬 자료구조] 쉘정렬(Shell sort) (0) | 2020.06.10 |
| [파이썬 자료구조] 삽입정렬 (0) | 2020.06.10 |